Python を使用して O(n) を視覚化します。-Python チュートリアル-php.cn

Python を使用して O(n) を視覚化します。

WBOY

リリース： 2023-09-02 17:25:01

転載

1134 人が閲覧しました

＃＃＃＃＃＃＃＃＃導入＃＃＃

コンピュータサイエンスとプログラミングの分野では、アルゴリズムの効率を理解することは、最適化され、高速に実行されるソフトウェアを作成するのに役立つため、非常に重要です。時間計算量は、入力サイズの増大に伴ってアルゴリズムの実行時間がどのように変化するかを測定するため、この文脈では重要な概念です。一般的に使用される時間計算量クラス O(n) は、入力サイズと実行時間の間の線形関係を表します。

＃＃＃意味＃＃＃

コンピュータサイエンスにおけるアルゴリズムの複雑さは、アルゴリズムの入力サイズに基づいて、時間や空間の使用率など、必要なリソースを評価することです。さらに、入力サイズを考慮した場合のアルゴリズムの実行速度についての理解をサポートします。アルゴリズムの複雑さを記述するために使用される主な表記法は、Big O 表記法 (O(n)) です。

＃＃＃文法＃＃＃リーリー

「for」ループは、0 から「n-1」の範囲に基づいて特定の命令セットを実行し、各反復で 1 つまたは複数の操作を実行します。ここで、「n」は反復回数を表します。

O(n) 時間計算量では、入力サイズ 'n' が増加すると、実行時間も比例して増加します。「n」が増加すると、ループの反復回数とループを完了するのに必要な時間も比例して増加します。線形時間計算量は、入力サイズと実行時間の間に直接の比例関係を示します。

入力サイズ「n」に関係なく、任意のタスクまたはタスクのシーケンスをループ内で実行できます。ここで注目すべき主な点は、ループが「n」回の反復を実行するため、時間の計算量が線形になることです。

＃＃＃アルゴリズム＃＃＃

ステップ 1: 変数の合計を 0

に初期化する

ステップ 2: 提供されたリスト内の各要素を反復処理します

＃＃＃方法＃＃＃
方法 1: 描画時間と入力サイズの関係
方法 2: 描画操作と入力スケールの関係

方法 1: 時間と入力サイズの関係をプロットする

＃＃＃例＃＃＃リーリー＃＃＃出力＃＃＃

このコードは、さまざまな入力サイズでの `algo_time()` アルゴリズムの実行時間を測定するために使用されます。テストしたい入力サイズとそれに対応する実行時間をこれらのリストに保存します。

「for」ループを使用して、入力サイズの範囲を反復処理します。この場合、ループは 1000 から 11000 に近づくまで実行され、毎回 1000 ずつ増加します。さらに詳しく説明すると、「n」の値を 1000 から 10000 まで 1000 ずつ変化させてアルゴリズムを評価する予定です。
ループ内で、入力サイズごとに `algo_time()` 関数の実行時間を測定します。時間の追跡を開始するには、関数を呼び出す前に `time.time()` を使用し、関数の実行が終了したらすぐに停止します。次に、その期間を「execution_time」という変数に保存します。

指定された入力サイズ ('n') の各入力値とそれに対応する実行時間を、それぞれのリスト ('input_sizes' および 'execution_times') に追加します。

ループが完了すると、プロットの生成に必要なデータが得られます。「plt.plot(input_sizes,execution_times)」は、収集したデータを使用して基本的な折れ線グラフを生成します。 X 軸は、さまざまな入力サイズを表す「input_sizes」値を示します。

'plt.xlabel()' と 'plt.ylabel()' は、最終的にそれぞれ座標軸の意味をマークするために使用され、'plt.show()' 関数を呼び出すことでグラフィックを表示できるようになります。

このコードを実行すると、入力サイズ ('n') の増加に伴う実行時間の増加をグラフにプロットすることで視覚化できます。アルゴリズムの時間計算量が O(n) であると仮定すると、グラフをプロットすると、入力サイズと実行時間の間にほぼ直線の相関関係があると近似できます。

方法2:描画操作と入力サイズの関係使用Python可视化O(n)。

＃＃＃例＃＃＃リーリー＃＃＃出力＃＃＃

このコードは、さまざまな入力サイズの下で `algo_ops()` アルゴリズムによって実行される操作の数を分析するように設計されています。 `algo_ops()` 関数を利用すると、ゼロから指定された入力パラメーター 'n' までの範囲内のすべての値の合計を計算し、同時に各計算中に実行されたすべての操作を追跡および記録できます。

最初に「matplotlib.pyplot」モジュールをインポートします。これにより、グラフなどの視覚化を作成できます。

次に、入力数値「n」を受け入れる algo_ops() 関数を定義します。関数内で、2 つの変数を初期化します。操作の数をカウントするための 'ops' と、数値の累積和を保存するための 'sum' です。

これらの配列には、調べたいディメンションと、それに対応する実行時間が格納されます。

反復ループを利用する 1 つの方法は、複数の入力スケールをループすることです。この場合、ループ実行範囲は1000～10000(11000を除く)となります。これは、1000 から 10000 までの 100 刻みの変数「n」を使用してテクニックを評価することを意味します。

ループ内で、すべての入力サイズに対する `algo_time()` プロセスのパフォーマンスを計算します。 `time.time()` を使用して、プロシージャを呼び出す前にストップウォッチを開始し、サブルーチンの実行が終了した直後にストップウォッチを終了します。次に、時間間隔を「execution_period」という変数に保存します。

各入力サイズについて、「input_sizes」というリストに入力 (「n」) の値を含めます。さらに、対応する処理時間を「execution_times」コレクションに追加します。

ループが完了すると、チャートを作成するために必要な基礎データが蓄積されます。ステートメント「plt.plot(input_sizes,execution_times)」は、収集されたデータを使用して基本的な折れ線グラフを作成します。「input_sizes」の値は X 軸に表示され、さまざまな入力サイズを表します。「execution_times」の値は縦軸に表示され、さまざまな入力サイズで「algo_time()」関数を実行するのに必要な時間を表します。

最後に、「plt.xlabel()」と「plt.ylabel()」を使用して座標系にラベルを付け、各軸の意味を示します。次に、「plt.show()」関数を実行してグラフを表示します。

プログラムを実行すると、入力 ('n') のサイズが大きくなるにつれて処理時間がどのように増加するかがグラフに表示されます。

＃＃＃結論は＃＃＃