algorithm - Big-O 記法が失敗するのはいつですか?

Question

Big-O記法[1]が実際に失敗する例は何ですか?

つまり、アルゴリズムの Big-O 実行時間から、アルゴリズム A がアルゴリズム B よりも高速であると予測されるのはいつで、実際にアルゴリズム B を実行するとアルゴリズム B の方が高速になるのでしょうか?

もう少し広い: アルゴリズムのパフォーマンスの不一致に関する理論的予測で実行時間が観察されるのはいつですか? Big-O 以外の予測は、検索ツリーの平均/予想回転数、または並べ替えアルゴリズムの比較数に基づく場合があり、係数と要素数の積として表されます。

明確化:

一部の回答が述べていることにもかかわらず、Big-O 表記はアルゴリズムのパフォーマンスを予測することを目的としています。とはいえ、これは欠陥のあるツールです。漸近的なパフォーマンスについてのみ話し、定数要因をぼやけさせます。これには理由があります。アルゴリズムを実行するコンピューターに関係なく、アルゴリズムのパフォーマンスを予測するためです。

私が知りたいのはこれです: このツールの欠陥はいつ現れますか? Big-O 記法はそれなりに便利ですが、完璧にはほど遠いことがわかりました。落とし穴、エッジケース、落とし穴は何ですか?

私が探しているものの例: バイナリヒープの代わりにフィボナッチヒープを使用してダイクストラの最短パスアルゴリズムを実行すると、n に対して O(m + n log n) 時間と O((m+n) log n) 時間が得られます。頂点と m 個の辺。遅かれ早かれ、フィボナッチヒープによる速度の向上を期待するでしょうが、私の実験では速度の向上は実現しませんでした。

(証明なしの実験的証拠は、一様にランダムなエッジの重みで動作するバイナリヒープが O(log n) 時間ではなく O(1) 時間を費やすことを示唆しています。 DecreaseKey の呼び出し回数)。

[1] 実際、失敗するのは表記法ではなく、表記法が表す概念と、アルゴリズムのパフォーマンスを予測するための理論的アプローチです。</反ペダントリー>

受け入れられた答えについて：

私が望んでいた種類の回答を強調する回答を受け入れました。同じくらい良い多くの異なる答えが存在します:)私が答えについて気に入っているのは、Big-O表記が「失敗」するとき（キャッシュミスが実行時間を支配するとき）の一般的なルールを示唆していることです。これにより、理解が深まる可能性があります（ある意味でATM の最適な表現方法がわかりません)。

score 105 · Accepted Answer

まさに 1 つのケースで失敗します: 人々が意図されていない何かのためにそれを使用しようとしたとき。

アルゴリズムがどのようにスケーリングするかを示します。それがどれほど速いかはわかりません。

Big-O 記法では、特定のケースでどのアルゴリズムがより高速になるかはわかりません。十分に大きな入力の場合、一方が他方よりも高速になることを示しているだけです。

score 27 · Accepted Answer

N が小さい場合、定数因子が支配的になります。5 つの項目の配列で項目を検索する方が、ハッシュテーブルで検索するよりもおそらく高速です。

score 17 · Accepted Answer

簡単な答え: n が小さい場合。巡回セールスマン問題は、目的地が 3 つしかない場合はすぐに解決されます (ただし、1 兆個の要素のリストから最小の数を見つけるには、O(n) ですが、しばらく時間がかかります)。

score 14 · Accepted Answer

標準的な例はクイックソートで、最悪の時間は O(n^2) ですが、ヒープソートは O(n logn) です。ただし、実際には、クイックソートは通常、ヒープソートよりも高速です。なぜ？2 つの理由:

クイックソートの各反復は、ヒープソートよりもはるかに単純です。さらに、単純なキャッシュ戦略によって簡単に最適化できます。
最悪の場合、ヒットするのは非常に困難です。

しかし、私見ですが、これは決して「ビッグオーが失敗する」という意味ではありません。最初の要素 (反復時間) は、見積もりに簡単に組み込むことができます。結局のところ、大きな O 数には、このほぼ一定の係数を掛ける必要があります。

平均ではなく償却された数値を取得すると、2 番目の要因は解消されます。推定するのは難しいかもしれませんが、より完全なストーリーを伝えます

score 11 · Accepted Answer

Big O が失敗する領域の 1 つは、メモリアクセスパターンです。Big O は、実行する必要のある操作のみをカウントします。アルゴリズムによってキャッシュミスが増えたり、ディスクからページインする必要のあるデータが発生したりすると、追跡できません。N が小さい場合、通常、これらの効果が支配的になります。たとえば、100 個の整数の配列を介した線形検索は、メモリアクセスのために、100 個の整数のバイナリツリーを介した検索よりもおそらく打ち負かされます。ツリーノードごとにキャッシュミスが発生しますが、線形検索ではルックアップごとにほとんどがキャッシュにヒットします。

score 9 · Accepted Answer

Big-O は、アルゴリズムの効率/複雑さを表すものであり、特定のコードブロックの実装の実行時間を表すとは限りません。これは Big-O が失敗するという意味ではありません。これは、実行時間を予測するためのものではないことを意味します。

Big-O の優れた定義については、この質問への回答をご覧ください。

score 9 · Accepted Answer

ほとんどのアルゴリズムには、「平均的なケース」と「最悪のケース」があります。データが常に「最悪のケース」のシナリオに陥る場合、理論的には平均的なケースでは効率が低くても、別のアルゴリズムがデータに対してより効率的であることが証明される可能性があります。
一部のアルゴリズムには、データを活用できる最良のケースもあります。たとえば、一部のソートアルゴリズムは理論上は非常に効率的ですが、データが既にソートされている (またはほとんどソートされている) 場合は、実際には非常に高速です。別のアルゴリズムは、一般的なケースでは理論的には高速ですが、データが既にソートされているという事実を利用できず、実際にはパフォーマンスが低下する可能性があります。
非常に小さなデータセットの場合、理論上の効率が優れているアルゴリズムでも、「k」値が大きいため、実際には効率が低下することがあります。

score 7 · Accepted Answer

1つの例（私は専門家ではありません）は、線形計画法のシンプレックスアルゴリズムは、実際にはうまく機能しますが、任意の入力で最悪の場合の複雑さが指数関数的になるということです。これに対する興味深い解決策は、「平滑化された複雑さ」を考慮することです。これは、任意の入力の小さなランダムな摂動を調べることで、最悪の場合と平均的な場合のパフォーマンスをブレンドします。

Spielman と Teng (2004)は、シャドウ頂点シンプレックスアルゴリズムが多項式平滑化された複雑さを持つことを示すことができました。

score 5 · Accepted Answer

Big Oは、たとえば、アルゴリズムAがアルゴリズムBよりも高速に実行されるとは言いません。入力が大きくなると、アルゴリズムAが使用する時間またはスペースはアルゴリズムBとは異なる速度で大きくなると言えます。ただし、特定の入力サイズの場合、大きなO表記は、あるアルゴリズムのパフォーマンスを別のアルゴリズムと比較して何も示しません。

たとえば、Aは操作ごとに遅くなる可能性がありますが、Bよりもbig-Oの方が優れています。Bは入力が小さいほどパフォーマンスが高くなりますが、データサイズが大きくなると、Aが速くなるカットオフポイントがあります。Big-O自体は、そのカットオフポイントがどこにあるかについては何も述べていません。

score 5 · Accepted Answer

The general answer is that Big-O allows you to be really sloppy by hiding the constant factors. As mentioned in the question, the use of Fibonacci Heaps is one example. Fibonacci Heaps do have great asymptotic runtimes, but in practice the constants factors are way too large to be useful for the sizes of data sets encountered in real life.

Fibonacci Heaps are often used in proving a good lower bound for asymptotic complexity of graph-related algorithms.

Another similar example is the Coppersmith-Winograd algorithm for matrix multiplication. It is currently the algorithm with the fastest known asymptotic running time for matrix multiplication, O(n^2.376). However, its constant factor is far too large to be useful in practice. Like Fibonacci Heaps, it's frequently used as a building block in other algorithms to prove theoretical time bounds.

score 4 · Accepted Answer

小さな N - 今日のコンピューターでは、100 は小さすぎて心配できない可能性があります。
隠された乗数 - IE マージとクイックソート。
病理学的ケース - 繰り返しますが、マージとクイック

score 4 · Accepted Answer

これは、Big-O が何を測定しているかによって多少異なります。最悪のシナリオの場合、実行時のパフォーマンスが Big-O が提案するよりもはるかに優れているという点で、通常は「失敗」します。それが平均的なケースであれば、それははるかに悪いかもしれません。

アルゴリズムへの入力データに何らかの事前情報がある場合、Big-O 記法は通常「失敗」します。多くの場合、Big-O 表記は、データが完全にランダムであるか完全に非ランダムである場合によく発生する、最悪の場合の複雑さを指します。

例として、プロファイリングされたアルゴリズムにデータをフィードし、ビッグオーがランダム化されたデータに基づいているが、データの構造が非常に明確に定義されている場合、結果の時間は予想よりもはるかに速くなる可能性があります。同様に、平均的な複雑さを測定していて、ひどくランダム化されたデータをフィードすると、アルゴリズムのパフォーマンスが予想よりもはるかに悪くなる可能性があります。

score 3 · Accepted Answer

Big-Oh表記が失敗する広い領域の1つは、データの量が使用可能なRAMの量を超えた場合です。

例としてソートを使用すると、ソートにかかる時間は、比較またはスワップの数によって支配されません（最適な場合、それぞれO（n log n）とO（n）があります）。時間の長さは、ディスク操作の数（ブロック書き込みとブロック読み取り）によって決まります。

使用可能なRAMを超えるデータを処理するアルゴリズムをより適切に分析するために、ディスク読み取りの数をカウントするI/Oモデルが誕生しました。その中で、次の3つのパラメータを検討します。

要素の数、N;
メモリの量（RAM）、M（メモリに含めることができる要素の数）。と
ディスクブロックのサイズB（ブロックあたりの要素数）。

特にディスク容量はありません。これは無限であるかのように扱われます。典型的な追加の仮定は、M>B2であるということ^です。

並べ替えの例を続けると、通常、I / Oの場合はマージソートを使用します。要素をサイズθ（M）のチャンクに分割し、メモリ内で並べ替えます（たとえば、クイックソートを使用）。次に、各チャンクから最初のブロックをメモリに読み込んでそれらのθ（M / B）をマージし、すべての要素をヒープに詰め込み、それらのBを選択するまで最小の要素を繰り返し選択します。この新しいマージブロックを書き出して続行します。メモリに読み込んだブロックの1つを使い果たした場合は、同じチャンクから新しいブロックを読み込んで、ヒープに入れます。

（すべての式は大きいθとして読み取る必要があります）。N / Mでソートされたチャンクを形成し、それをマージします。N / M回のログ（ベースM / B）をマージします。すべてのN/Bブロックを読み書きするたびに、N / B *（N/Mの対数ベースM/B）の時間がかかります。

メモリ内の並べ替えアルゴリズム（ブロックの読み取りとブロックの書き込みを含めるように適切に変更）を分析して、私が提示したマージ並べ替えよりもはるかに効率が悪いことを確認できます。

この知識は、Arge and Brodal（http://daimi.au.dk/~large/ioS08/）による私のI/Oアルゴリズムコースの好意によるものです。また、理論を検証する実験も行いました。メモリを超えると、ヒープソートには「ほぼ無限の」時間がかかります。クイックソートは耐えられないほど遅くなり、マージソートはほとんど耐えられないほど遅くなり、I / O効率の高いマージソートはうまく機能します（最高の結果です）。

score 1 · Accepted Answer

Robert Sedgewick は、アルゴリズムの分析に関する Coursera コースで big-O 表記の欠点について語っています。彼は銀河系アルゴリズムの例を特に悪質なものと呼んでいます。なぜなら、それらは前任者よりも優れた複雑さのクラスを持っているかもしれませんが、実際にそれを示すには天文学的なサイズの入力が必要になるからです。

https://www.cs.princeton.edu/~rs/talks/AlgsMasses.pdf

score 1 · Accepted Answer

データがモデルに適合しない場合でも、big-o 表記は機能しますが、最良のシナリオと最悪のシナリオの重複が見られます。

また、一部の操作は、線形データアクセスとランダムデータアクセスに合わせて調整されているため、1 つのアルゴリズムはサイクルの点では優れていますが、呼び出し方法が設計から変更された場合、非常に遅くなる可能性があります。同様に、アルゴリズムがメモリにアクセスする方法が原因でページ/キャッシュミスが発生した場合、Big-O はプロセスの実行コストを正確に見積もることはできません。

どうやら、私が忘れていたように、Nが小さいときも:)

score 1 · Accepted Answer

この質問は、「人の IQ が実際に落ちるのはいつですか?」と尋ねるようなものです。IQが高いからといって人生で成功するわけではなく、IQが低いからといって滅びるわけではないことは明らかです. それでも、たとえそれが絶対的なものでなくても、可能性を評価する手段として IQ を測定します。

アルゴリズムでは、Big-Oh 表記によってアルゴリズムの IQ が得られます。アルゴリズムが特定の状況で最適に機能することを必ずしも意味するわけではありませんが、このアルゴリズムが優れた可能性を秘めていることを示す数学的な根拠があります。Big-Oh 記法でパフォーマンスを測定するのに十分である場合、実行時テストが少なくなり、パフォーマンスが大幅に向上します。

Big-Oh は、良いか悪いかの特定の尺度ではなく、範囲と考えてください。最良のシナリオと最悪のシナリオがあり、その間には膨大な数のシナリオがあります。Big-Oh の範囲内にどれだけ適合するかによってアルゴリズムを選択しますが、パフォーマンスを測定するための絶対的なものとして表記法に依存しないでください。

score 1 · Accepted Answer

簡単に言えば、大量のメモリを使い始めるときは、常に最新のハードウェアを使用してください。教科書では、メモリアクセスは均一であると想定されていますが、もはやそうではありません。もちろん、不均一なアクセスモデルに対して Big O 分析を行うこともできますが、それはやや複雑です。

n が小さい場合は明らかですが、興味深いものではありません。

実際には、Delphi、Java、C#、および Smalltalk の標準コレクションを数百万のオブジェクトで使用する際に問題が発生しました。そして、支配的な要因がハッシュ関数または比較であることが証明された小さなもので

algorithm - Big-O 記法が失敗するのはいつですか?

18 に答える 18

Related

Reference