6

O（x）表記を使用してアルゴリズムの速度を推定しようとすると、完全にだまされることがあります。つまり、順序がO（n）またはO（mxn）の場合は実際に指摘できますが、O（lg（ n））またはO（C（power n））何かが足りないと思います...では、アルゴリズムをすばやく見落としながら簡単に見積もるためのヒントとコツは何ですか？

私が探しているものの例として、ここに簡単なもののいくつかがあります（間違っている可能性がありますが、最善を尽くしています）：

  • O（n）：1からnまでの単純なループがある場合（またはそれらのいくつかであるが、ネストされていない場合。
  • O（mxn）：制限がmとnである別の内部のネストされたループ。

前もって感謝します。

4

8 に答える 8

7

これが役立つかもしれないブログ投稿です：

物事を分解して元に戻すためのコスト

その投稿は、big-O注文を処理するための「マスター定理」を説明しています。

于 2009-02-10T13:28:43.810 に答える
7

再帰的な分割統治アルゴリズムは、多くの場合 O(logN) です。分割統治をループするアルゴリズムは O(NlogN) です。

于 2009-02-10T13:20:38.963 に答える
4

O(lg(n)) : アルゴリズムの各ステップで n (多くの場合 n/2) の割合で問題が小さくなり、各ステップで一定量の作業が行われる場合。二分探索は良い例です。各ステップでは一定量の作業 (中間点を計算して 1 つの比較を行う) を行うことで問題のサイズが半分になるためです。

n がその比率の上にあることに注意してください。これは、問題のサイズが各ステップで 1/n ずつ減少することとは異なります。:)

于 2009-02-10T13:21:34.483 に答える
1

アルゴリズムの実行時間を見積もる簡単な方法を探しているなら、他の答えが良いでしょう。より詳細な回答が必要な場合は、「マスター定理」を参照することをお勧めします。ドイツの記事には、それにぴったりの表があります。

編集：ジョンD.クックは、マスター定理の素晴らしい要約を作成しました。彼の答えのリンクを参照してください。

于 2009-02-10T13:29:02.000 に答える
1

Big O Notationに関するウィキペディアの記事には、一般的な関数の順序の優れたチャートがあります。

于 2009-02-10T13:33:14.503 に答える
1

通常、データのサイズが N であるため、O(logN) のようなものが発生しますが、ツリーの深さが logN であるツリーなどで編成されます。典型的な検索でルートからリーフに移動する場合 (最悪の場合)、アルゴリズムが O(logN) になることは容易にわかります。

厳格なルールはありません。それぞれのケースを見て、最悪のシナリオを把握し、そのコストを計算するだけです。

于 2009-09-27T07:37:00.360 に答える
1

アルゴリズムの漸近的な複雑さは実際には重要です。私が自分のコードや他の人のコードをレビューするときに使用する経験則のいくつかを次に示します。通常、実用的なコンピューター アルゴリズムは、多くの変数と自明でないデータ構造の関数ですが、(説明のためだけに) アルゴリズム f が基本的に単一の整数 X を引数として取り、f の漸近的な複雑さをX. f(0) が自明であるとします。次に、一般的に：

  • 0 から X までのすべての入れ子になったループは X に指数を追加するため、2 つのループ (一方が別の内側に入れ子になっている) は X**2 (2 次) を与えます。
  • f(X) が f(X-1) を末尾再帰的に呼び出す場合、通常は反復、つまり単一の外部ループ (O(X)) に対応します。
  • 著者が繰り返しとして意図したルーチンを見たことがありますが、0..X からの繰り返しと X-1 への末尾再帰の両方があります。これらは 2 次動作 (O(X**2)) になります。
  • f(X) が f(X-1) を 2 回以上呼び出すと、指数アルゴリズムになり、それから O(2**X) が得られます。
  • f(X) が f(X/2) を 2 回呼び出す場合、複雑さに関しては 1 回の反復に対応します (これは分割統治アルゴリズムです)。(詳細によってはO(X log X)やO(X)となるが、1回の繰り返しと考えていることに気付く。)
  • f が適切に実装された順序付きデータ構造 (順序付きセット、優先度ヒープなど) を使用し、アルゴリズムがデータ構造におよそ X 個のオブジェクトを追加する場合、操作は O(log X) になります。したがって、一定数のデータ構造操作がループ内で行われる場合、たとえば、O(X * log X) が得られます。
  • 順序付けられたデータ構造が不適切に実装されている場合、個々の操作で O(log X) ではなく O(X) が取得される可能性があります。

いくつかの特殊なケース:

  • 文字列またはメモリ領域に追加することによって拡張するアルゴリズムは、多くの言語で O(X**2) オーバーヘッドを引き起こします。

    for (i = 0; i < X; i++) { s += "foo"; } // quadratic

  • この典型的なネストされたループには、X**2 のオーバーヘッドもあります。

    for (i = 0; i < X; i++) { for (j = 0; j < i; j++) { ... } } // quadratic

  • std::set や std::map などの C++ STL コンテナーには、ほとんどすべての操作で O(log X) のオーバーヘッドがあります。

  • strlen(s) およびその他の同様のカウント アルゴリズムが X を返す場合、O(X) オーバーヘッドがあります。
  • memcpy などは O(X) になります
  • リンクされたリストから等価比較によって要素を消去するなど、複雑な危険な操作があり、O(X) またはそれ以上の結果が得られます。
  • テンプレートベースのコンテナーを使用する場合は、比較、順序付けなどの演算子が高速であり、複雑な要素が隠れていないことを確認してください。
  • 参照カウントを使用する場合、長さが X である参照のリンク リストへの最後の参照を削除すると、参照の削除が最悪の O(X) 操作になる可能性があります。
  • オブジェクト指向言語で複雑なデータ構造をコピーすると、オブジェクトをコピーするためのルーチンが自明ではなく、たとえばグローバル オブジェクト セットを更新する場合、奇妙な漸近的な複雑さが生じる可能性があります。

ちょうど私の2セント！お役に立てれば！

于 2009-02-12T06:32:39.080 に答える