2

重複の可能性:
複雑さ。定数が重要でないのはなぜですか?

コード/アルゴリズムの複雑さについて簡単な質問があります。入力に対する成長の順序、O(n) が O(n^2) よりも優れている理由など、基本的な複雑さの概念をかなりよく理解しています。ただし、定数が本当に重要かどうかはわかりません。私には、それらはすべきであるが、誰もそれらを考慮したり、それらについて話したりすることはありません. 同じ複雑さのコードを改善できますか。O(n)としましょう。このコードが特定の入力に対して 10 分で実行されるとしましょう。コードを 2 回繰り返して、コードが 20 分で実行されるとどうなりますか。複雑さは同じですが、10分以上20分は大したことです。同じ複雑さに関係なく、これらのことは重要ですか? そうでない場合、なぜですか?はいの場合、なぜですか? 説明してください。

4

6 に答える 6

4

理論的な複雑さの分析では、係数はまったく問題になりません。実際には、それらは非常に重要です。これが、最適化問題に (多項式の複雑さ) 内点アルゴリズムではなく、(指数関数的な複雑さの) シンプレックス アルゴリズムを使用する理由です。

アルゴリズム分析を行っていて、O() の動作を知りたい場合、定数は関係ありません。特定の範囲の問題に対してどのコードがより速く実行されるかを知りたい場合は、すべてが重要です。

于 2012-10-25T03:39:14.993 に答える
3

複雑さの本当の概念とパフォーマンスのさまざまな例を混ぜ合わせていると思います。複雑さとは、つまり、n が大きくなると、処理ステップの成長の順序はどうなるかということです。

たとえば、線形検索を実行していて、この場合の順序は O(n) であるとします。ここでの意味は次のとおりです。n = 5 で 5 秒かかる場合、n=10 の場合は 10 秒かかります。つまり、関係は線形です。

順序が O(5n) の場合、違いはありません。つまり、n=5 の場合は同じ検索に 25 秒かかり、n=10 の場合は 50 秒かかります。私はまだ言うことができます、その O(n) つまり直接依存しています。

同じ例は、O(n^2) の並べ替えアルゴリズムにも当てはまります。

あなたの例では、言及された改善は重要ですが、複雑さの順序、つまり関係は変わりません。処理時間を 2 分の 1 に短縮できれば、大幅な改善nになります。たとえば、時間が 20 分から 10 分に短縮されました。アルゴリズムを変更して、成長したnとの時間の関係を変更すると、O(n)も変更されます:)

于 2012-10-25T03:39:51.597 に答える
1

入力サイズが大きくなるにつれて関数がどのようにスケーリングするかだけに関心がある複雑性理論にとっては問題ではありません。

定数は、入力サイズが無限大に向かって大きくなったときの関数の動作にはまったく影響しません。

ただし、特定のコードを実際に実行することに関心がある場合は、大きな一定のオーバーヘッドと、小さい入力サイズで関数がどのように機能するかについて非常に関心があるかもしれません。

複雑さの理論と実践の違い。

これは、この質問に対する良い答えです。

複雑。定数が重要でないのはなぜですか?

于 2012-10-25T03:40:10.273 に答える
1

もちろん、必要な速度の 2 倍のアルゴリズムを作成することは重要です。要点は、「n」は非常に大きくなる可能性があるため、「n」の観点からアルゴリズムのパフォーマンスを気にするということです。

実際の例を見てみましょう。n 個の項目のリストがあるとします。アルゴリズムは、リストを 1 回繰り返します。それがn次です。リストを 2 回反復すると、時間がかかり、遅くなる可能性があります。不要な場合は、これを行うべきではありません。

しかし、n^2 アルゴリズムを使用すると、長期的には 2*n アルゴリズムよりもはるかに大きな影響があります。n が大きくなるにつれて、n^2 と 2*n の差はますます大きくなります。

あなたの質問に答えると、はい、プログラムの実行速度が 2 倍になると問題になります。しかし、それが指数関数的に遅い場合、それはもっと重要です。だからこそ、私たちはBig-Ohを大切にしています。しかし、速度の改善は明らかにプログラムにとって良いことです。

于 2012-10-25T03:42:26.573 に答える
1

これは、理論と実践の大きな違いです。これには、考慮すべき点がいくつかあります。

  • 定数は、実際の実装では明確でない場合があります。通常、特定の実装からこれらの定数を決定することはできません。たとえば、同じ問題に対して 2 つの O(N) アルゴリズムがあるとします。ただし、1 つは 2N 操作が必要で、2 つ目は N 操作しか必要ありません。N 回の操作を行う方が高速に実行されると考える人もいるかもしれませんが、そうではない可能性があります。より良いキャッシュやパイプラインの使用などのために、それぞれ 1 サイクルしかかからない 2N 操作があるかもしれませんが、他のアルゴリズムはそれぞれ 4 サイクルで N 操作を取るかもしれません。したがって、より多くの操作を行うアルゴリズムは、依然として高速である可能性があります。別のハードウェアでは、これは非常に異なって見える場合があります。したがって、正確なハードウェアを知らない限り、理論的な分析は非常に優れたガイドです。通常、実際のハードウェアでは相互作用が非常に複雑であるため、ベンチマークだけが良いヒントを与えてくれます。

  • リアルタイム システムの場合も、状況は大きく異なります。ここでは通常、アルゴリズムにかかる実際の時間を指す最悪ケース実行時間 (WCET) に関心があります。この場合、定数は非常に重要です。ただし、この場合、問題のサイズもわかっているため (通常は、2 つのセンサーからの入力のセット)、分析は大きく異なります。

  • ハードウェアの影響が非常に大きくなる可能性があるため、少なくとも関連するすべての問題サイズについて、理論的には悪く見えるアルゴリズムが、実際にははるかに良く見えるアルゴリズムよりも優れている可能性があります。これは、ツリーを使用するアルゴリズム (多くの場合、理論的には優れている) とフラットな配列構造を使用するアルゴリズム (多くの場合、理論的に悪い) の場合に当てはまります。ただし、通常はフラット配列の方がはるかに効率的にキャッシュできるため、より優れています。ただし、ヒープを配列として実装する場合など、両方の長所を活かすことができる場合があります (ほとんどの場合、これはソートされたツリーよりも優れています)。

于 2012-10-25T08:23:09.983 に答える
0

n が大きくなるにつれて O(n) を O(n^2) と比較すると、定数は無関係になり始めます。定数が大きい場合でも、それはかなり明白なはずです。

定数が言及されていない理由は、複雑さの順序がより重要だからです。アルゴリズムが線形時間であることがわかったら、詳細を調べながら自分で勾配を確認します。

O(n) 定数である 2 つのプログラムがある場合、どちらが優れているかを判断する際に重要になります。次に、アルゴリズムをより詳細に分析する必要があります。

于 2012-10-25T03:41:25.317 に答える