Big-O 表記法が失敗する場合は? 質問する

Big-O表記法[1]が実際には失敗する例にはどのようなものがありますか？

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

もう少し広い視点で言うと、アルゴリズムのパフォーマンスに関する理論的な予測が、観測された実行時間と一致するのはいつでしょうか。Big-O 以外の予測は、検索ツリー内の平均/予想回転数、またはソート アルゴリズム内の比較回数 (係数×要素数として表される) に基づく場合があります。

説明:

いくつかの回答に反して、Big-O記法ははアルゴリズムのパフォーマンスを予測することを目的としています。欠陥のあるツール: このツールは漸近的なパフォーマンスについてのみ言及しており、定数要素は不明瞭です。このツールがこれを行うのには理由があります。このツールは、アルゴリズムをどのコンピューターで実行するかに関係なく、アルゴリズムのパフォーマンスを予測することを目的としているからです。

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

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

(実験的証拠は証明されていませんが、一様にランダムなエッジ重みで動作するバイナリ ヒープは O(log n) 時間ではなく O(1) 時間を費やすことを示唆しています。これは実験の大きな落とし穴の 1 つです。数えるのが難しいもう 1 つの落とし穴は、DecreaseKey への呼び出しの予想回数です)。

[1] 実際にはそうではない表記それは失敗するが、概念この表記法は、アルゴリズムのパフォーマンスを予測するための理論的アプローチを表しています。

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

私が期待していた種類の回答を強調するために、回答を受け入れました。同じように優れたさまざまな回答が存在します :) この回答で気に入っているのは、Big-O 表記が「失敗する」場合 (キャッシュ ミスが実行時間を支配する場合) の一般的なルールが示唆されており、理解を深めることもできる点です (ある意味で、現時点では最適な表現方法がわかりません)。