На каких примерах нотация Big-O [1] не работает на практике?

То есть, когда время выполнения алгоритмов Big-O предсказывает алгоритм A быстрее, чем алгоритм B, но на практике алгоритм B быстрее при его запуске?

Чуть шире: когда теоретические прогнозы о несоответствии производительности алгоритма наблюдаются во время выполнения? Прогноз не-Big-O может основываться на среднем / ожидаемом числе вращений в дереве поиска или количестве сравнений в алгоритме сортировки, выраженном как коэффициент, умноженный на количество элементов.

осветление:

Несмотря на то, что некоторые ответы говорят, обозначение Big-Oявляется предназначен для прогнозирования производительности алгоритма. Тем не менее, этонедостатки инструмент: он говорит только об асимптотике и размывает постоянные факторы. Он делает это по причине: он предназначен для прогнозирования алгоритмической производительности независимо от того, на каком компьютере вы выполняете алгоритм.

То, что я хочу знать, это: когда недостатки этого инструмента показывают себя? Я обнаружил, что запись Big-O довольно полезна, но далека от совершенства. Каковы подводные камни, крайние случаи, ошибки?

Пример того, что я ищу: запуск алгоритма кратчайшего пути Дейкстры с кучей Фибоначчи вместо двоичной кучи, вы получите время O (m + n log n) против O ((m + n) log n), для n вершины и m ребер. Рано или поздно вы ожидаете увеличения скорости от кучи Фибоначчи, но в моих экспериментах увеличение скорости никогда не материализовалось.

(Экспериментальные данные, без доказательств, предполагают, что двоичные кучи, работающие на равномерно случайных весах ребер, тратят O (1) времени, а не O (log n); это одна большая ошибка для экспериментов. Еще одна, которую сука считает, - это ожидаемая количество звонков на DecreaseKey).

[1] На самом деле это необозначение что не получается, ноконцепции обозначение означает и теоретический подход к прогнозированию производительности алгоритма. </ Анти-педантизм>

На принятый ответ:

Я принял ответ, чтобы выделить ответы, на которые я надеялся. Существует много разных ответов, которые так же хороши :) Что мне нравится в ответе, так это то, что он предлагает общее правило для случая, когда нотация Big-O «терпит неудачу» (когда отсутствует кэш, доминирует во времени выполнения), что также может улучшить понимание (в некотором смысле Я не уверен, как лучше всего экспресс банкомат).