アルゴリズムの複雑性分析の概要（パート2）

翻訳者から：このテキストは、材料を過度に「噛む」場所のために、小さな略語で示されています。 著者は、読者には特定のトピックが単純すぎる、または有名すぎるように見えるかもしれないと正しく警告しています。 それにもかかわらず、個人的には、このテキストは、アルゴリズムの複雑さの分析に関する既存の知識を合理化するのに役立ちました。 他の誰かに役立つことを願っています。
元の記事の量が多いため、私はそれを部分に分割しましたが、そのうち合計4つになります。
私は（いつものように）翻訳の品質の改善に関するPMのコメントに非常に感謝します。

以前に公開された：
パート1

難易度

前の部分から、これらの装飾定数をすべて破棄できる場合、プログラム命令をカウントするための関数の漸近的な動作について話すことは非常に簡単になると結論付けることができます。 実際、ループを含まないプログラムにはf( n ) = 1があります。この場合、一定数の命令が必要なためです（もちろん、再帰がない場合-以下を参照）。 1からnまでの単一サイクルは、サイクルの前後で不変の数のコマンドを実行し、サイクル内の一定数の命令がn回実行されるため、漸近f( n ) = n nを与えます。

そのような考慮事項に導かれるのは、毎回指示を読むよりも面倒ではないので、この資料を統合するためのいくつかの例を見てみましょう。 次のPHPプログラムはAサイズn配列A特定の値が含まれているかどうかを確認します。

 <?php $exists = false; for ( $i = 0; $i < n; ++$i ) { if ( $A[ $i ] == $value ) { $exists = true; break; } } ?> 

配列内の値を見つけるこの方法は、 線形検索と呼ばれます 。 プログラムにはf( n ) = nがあるため、これは有効な名前です（より正確には「線形」を意味します。次のセクションで検討します）。 break使用すると、1回の反復の後でも、プログラムをより早く終了できます。 ただし、配列A特定の値がまったく含まれていない最も不利なシナリオに関心があることを思い出してください。 したがって、 f( n ) = nは以前と同じです。



配列から2つの値を追加し、その結果を新しい変数に書き込むPythonプログラムを見てみましょう。

 v = a[ 0 ] + a[ 1 ] 

ここには一定数の命令があるため、 f( n ) = 1です。

次のC ++プログラムはAサイズnベクトル（元の配列） A 2つの同一の値が含まれているかどうかを確認します。

 bool duplicate = false; for ( int i = 0; i < n; ++i ) { for ( int j = 0; j < n; ++j ) { if ( i != j && A[ i ] == A[ j ] ) { duplicate = true; break; } } if ( duplicate ) { break; } } 

ネストされた2つのサイクルは、 f( n ) = n ^2の形の漸近を与えます。

---

実用的な推奨事項 ：単純なプログラムは、ネストされたサイクルの数をカウントすることで分析できます。 n回の繰り返しでの単一サイクルにより、 f( n ) = nます。 ループ内のループはf( n ) = n ²です。 サイクル内のサイクル内のサイクルはf( n ) = n ³です。 などなど。

---

ループ本体のプログラムで関数が呼び出され、その中で実行された命令の数がわかっている場合、プログラム全体のコマンドの総数を簡単に判断できます。 例として次のCコードを検討してください。

 int i; for ( i = 0; i < n; ++i ) { f( n ); } 

f( n )が正確にn命令を実行することがわかっている場合、 f( n )はn回呼び出されるため、プログラム全体の命令数は漸近的にn ²に近づくと言えます。

---

実用的な推奨事項 ：一連のforループが連続している場合、プログラムの漸近的な動作がそれらの中で最も遅いループを決定します。 1つに続く2つのネストされたループは、ネストされたループ自体と漸近的に同じです。 ネストされたループは、単一ループを支配すると言われています。

---

次に、理論家が使用する興味深い表記法に切り替えましょう。 fの正確な漸近性を見つけると、プログラムはΘ( f( n ) )と言います。 たとえば、上記の例では、プログラムΘ( 1 ) 、 Θ( n ² )およびΘ( n ² )がそれぞれプログラムです。 Θ( n ) 「theta from n」 Θ( n )発音されます。 f( n ) （定数を含む命令をカウントする元の関数）はΘ( - )と言うこともあります。 たとえば、 f( n ) = 2nはΘ( n )関数であると言えます。 一般的に、新しいものは何もありません。 また、 2n ∈ Θ( n )と発音することもできます。これは「two nはthen from the n」に属します。 このような表記法と混同しないでください。プログラムに必要なコマンドの数を数えて2nにすると、このアルゴリズムの漸近的な動作はn （定数を破棄することでわかります）として記述されているだけです。 この表記法を使用して、いくつかの真の数学的ステートメントを示します。

1. n ⁶ + 3n∈Θ（n ⁶ ）
2. 2 ⁿ + 12∈Θ（2 ⁿ ）
3. 3 ⁿ + 2 n∈Θ（3 ⁿ ）
4. n ⁿ + n∈Θ（n ⁿ ）

ところで、最初のパートの1つを実行することにした場合、これは彼の正解です。

この関数（つまりΘ( )を記述するもの）を時間の複雑さ 、または単にアルゴリズムの複雑さと呼びます。 したがって、 Θ( n )アルゴリズムの複雑さはnです。 Θ( 1 ) 、 Θ( n ) 、 Θ( n ² )およびΘ( log( n ) )にも特別な名前がありΘ( log( n ) ) 。これらは非常に一般的です。 彼らは、 Θ( 1 )は一定時間アルゴリズム、 Θ( n )は線形 、 Θ( n ² )は2次 、 Θ( log( n ) )は対数であると言います（何がわからなくても心配しないでくださいΘ( log( n ) )対数-これについてはすぐに説明します）。

---

実用的な推奨事項 ： Θが大きいプログラムは、 Θが小さいプログラムよりも実行が遅くなります。

---

「big O」という表記

実際には、上記で検討した方法でアルゴリズムの正確な動作を見つけるのは難しい場合があります。 特に複雑な例の場合。 しかし、私たちのアルゴリズムの振る舞いは決して境界を越えることはありません。 これにより、定数を無視しても（以前のように）アルゴリズムの速度が明確に示されない場合があるため、作業が楽になります。 必要なのはこの境界を見つけることであり、その方法は例で説明する方が簡単です。

学習アルゴリズムで使用される最もよく知られているタスクはソートです。 サイズnの配列A n （おなじみのように聞こえますか？）。そして、それをソートするプログラムを書くように求められます。 ここでの関心は、そのような必要性が実際のシステムでしばしば生じることです。 たとえば、ファイルブラウザーは、ユーザーがファイルを簡単にナビゲートできるように、ファイルを名前で並べ替える必要があります。 または別の例：ビデオゲームでは、仮想世界でのプレイヤーの視点からの距離に応じて、画面に表示されている3Dオブジェクトを並べ替えるタスクが発生する場合があります。 目的：それらのうちのどれが彼に見え、どれが見えないかを決定します（これは可視性問題と呼ばれます）。 ソートも興味深いものです。なぜなら、ソートには多くのアルゴリズムがあり、そのいくつかは他のものよりも悪いからです。 このタスクは、定義と説明も簡単です。 それでは、配列をソートするコードを書きましょう。

 b = [] n.times do m = a[ 0 ] mi = 0 a.each_with_index do |element, i| if element < m m = element mi = i end end a.delete_at( mi ) b << m end 

Rubyで配列の並べ替えを実装する完全に非効率的な方法を次に示します。 （もちろん、Rubyは、使用すべき組み込み関数を使用した配列のソートをサポートしています。これらは、説明のためだけに示した上記のコードよりも間違いなく高速です。）

このメソッドは、選択によるソートと呼ばれます 。 まず、配列の最小要素が検出され（上記のコードではa 。最小値はm 、そのインデックスはmiとして示されます）、新しい配列の最後に配置され（この場合はb ）、元の配列から削除されます。 次に、残りの値の中で、最小値が再び検出され、新しい配列（現在2つの値を含む）に追加され、古い配列から削除されます。 すべての要素が元の配列から新しい配列に転送されるまで、このプロセスが繰り返されます。これは、ソートの終了を意味します。 この例では、2つのネストされたループがあります。 外側のループはn回「実行」され、内側のループは配列a各要素に対して1回実行されます。 最初にaはn要素があり、各反復でそれらの1つを削除してから、最初に内部ループがn回スクロールし、次にn - 1 、 n - 2など、最後の反復まで内部ループが1回だけ通過します。

合計1 + 2 + ... + (n - 1) + nを考慮すると、このコードの複雑さを見つけるのはやや問題になります。 しかし、それに対する「上限」を見つけることができます。 これを行うには、プログラムを変更して（コードに触れることなく精神的にできます）、それを悪化させてから、何が起こったかの複雑さを導き出します。 そうすれば、元のプログラムの動作がひどく、または（ほとんどの場合）良くなっていると自信を持って言うことができます。

次に、プログラムの複雑さの結論を単純化するために、プログラムを変更する方法について考えてみましょう。 忘れないでください：それを悪化させる（たとえば、コードに新しい命令を追加する）だけで、元のプログラムに対して評価が意味を持つようにすることができます。 明らかに、プログラムの内部ループを変更して、各反復でn回評価を強制することができます。 これらの繰り返しのいくつかは役に立たないでしょうが、結果のアルゴリズムの複雑さを分析するのに役立ちます。 この小さな変更を行うと、新しいアルゴリズムにはΘ( n ² )が含まれます。これは、それぞれが正確にn回実行される2つのネストされたループを取得するためです。 もしそうなら、元のアルゴリズムにはO( n ² )ます。 O( n ² ) 「 nからの大きなOの2乗」 )発音されます。 これは、プログラムが漸近的にn ²より悪くないことを示唆しています。 彼女は良くも良くも働くでしょう。 ところで、コードに実際にΘ( n ² )場合、それはまだO( n ² )であると言います。 これをよりよく理解するために、元のプログラムを変更してもそれほど変わらず、ほんの少しだけ悪くなると想像してください。 無駄な命令をプログラムの先頭に追加するようなもの。 これは、命令カウント関数の定数のみを変更しますが、漸近では無視します。 したがって、プログラムのΘ( n ² )もO( n ² )です。

しかし、その逆は必ずしも真実ではありません。 たとえば、 Θ( n )持つコードΘ( n ) 、 O( n )に加えてO( n )ます。 Θ( n )プログラムがn回実行さfor単なるforループであると想像するなら、別のfor insideを追加し、 n回繰り返すことで悪化させることができます。 これにより、 f( n ) = n ^2のプログラムが得られます。 要約： Θ( a )持つプログラムは、 bよりもb O( b )ほど悪いO( b )です。 また、変更は意味をなさないか、元のコードに似たコードを作成する必要がないことに注意してください。 彼に必要なのは、与えられたnに関して命令の数を増やすことだけです。 結果を使用して、問題を解決するのではなく、指示をカウントします。

したがって、プログラムにO( n ² )があると言っても、安全です。アルゴリズムの分析により、 n ²よりも悪くなることはありませんでした。 これにより、プログラムの速度を適切に見積もることができます。 新しい表記でより良くなるように、いくつかの例を解いてみましょう。





アルゴリズムの複雑度は、その真の複雑度の上限であるため、順番にΘで表されるため、 Θが正確な推定値を与えると言うことがあります。 見つけた境界が正確でないことがわかっている場合は、小文字のを使用してそれを示すことができます。 たとえば、アルゴリズムがΘ( n )場合、その正確な複雑度はnです。 したがって、このアルゴリズムは同時にO( n )とO( n ² )です。 アルゴリズムはΘ( n ) 、 O( n )は境界をより正確に定義します。 そして、 O( n ² )を( n ² ) （発音：「nの小さなo」と読みます)書くと、境界の非剛直性を知っていることを示すことができます。 もちろん、アルゴリズムの動作に関する詳細な情報を得るために、アルゴリズムの正確な境界を見つけることができる方が良いですが、残念ながら、これは必ずしも簡単ではありません。

---

実用的な推奨事項 ：アルゴリズムのO複雑度を見つけることは、そのΘ複雑度よりも簡単です。

---

今では、これらすべての新しい表記法と混同されているかもしれませんが、次の例に進む前に、さらに2つの文字を理解しましょう。 上記で、プログラムを変更して、O表記を作成するよりも悪化させました（命令数を増やし、実行時間を増やしました）。 は、コードが特定の制限より遅くなることは決してないことを教えてくれます。 これから、評価の基礎が得られます。プログラムは十分ですか？ 反対のことを行い、既存のコードを改善し 、何が起こるかの複雑さを見つける場合、Ω表記を使用します。 したがって、 Ωは複雑さをもたらしますが、これはプログラムを改善することはできません。 プログラムが遅いか、アルゴリズムが悪いことを証明したい場合に便利です。 また、この特定の場合に使用するにはアルゴリズムが遅すぎると言う場合にも使用できます。 たとえば、アルゴリズムがΩ( n ³ )ということは、アルゴリズムがn ³より良くないことを意味します。 Θ( n ³ ) 、またはΘ( n ⁴ ) 、またはそれより悪い場合もありますが、その「良さ」の限界はわかります。 したがって、 Ωは、アルゴリズムの複雑さの下限を示します。 οと同様に、この制限が厳密でないことがわかっている場合は、 ω書くことができます。 たとえば、 Θ( n ³ )アルゴリズムはο( n ⁴ )およびω( n ² )です。 Ω( n ) 「nから大きいオメガ」 Ω( n )発音され、 ω( n ) 「nから小さいオメガ」 ω( n )発音されます。



Θ代わりにOとΩを使用する理由は、見つかった境界の精度が不明な場合や、アルゴリズムを深く掘り下げたくない場合があるためです。

さまざまな表記法をすべて覚えていなくても心配する必要はありません。 いつでも戻って情報を更新できます。 最も重要な文字はOとΘです。

また、 Ωは関数の動作に下限を与えます（つまり、プログラムを改善して命令の計算を少なくする）が、最悪の場合の分析を参照していることに注意してください。 これは、最悪のデータセットをプログラムにフィードし、その動作を分析するためです。

次の表は、上記で示した記号と、数値を比較するための通常の数学アイコンとの関係をまとめたものです。 通常の数学表記の代わりにギリシャ文字を使用する理由は、通常ではなく漸近推定値の比較を扱っていることを示す必要があるからです。

漸近推定の比較演算子	数値比較演算子
アルゴリズムはo （何か）です	数<
O ( - )	≤ -
Θ ( - )	= -
Ω ( - )	≥ -
ω ( - )	> -

---

: , O , o , Ω , ω Θ , O , , Θ , , Ω .

---