Когда запись Big-O терпит неудачу?

Question

Какие есть примеры, когда нотация 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 «терпит неудачу» (когда отсутствует кэш, доминирует во времени выполнения), что также может улучшить понимание (в некотором смысле Я не уверен, как лучше экспресс-банкомат).

Answer 1

Сбой происходит ровно в одном случае: когда люди пытаются использовать его для чего-то, для чего он не предназначен.

Он рассказывает, как масштабируется алгоритм. Это не говорит вам, как быстро.

Нотация Big-O не говорит вам, какой алгоритм будет быстрее в любом конкретном случае. Это только говорит о том, что при достаточно большом вводе один будет быстрее другого.

Answer 2

Когда N мало, постоянный фактор доминирует. Поиск элемента в массиве из пяти элементов, вероятно, быстрее, чем поиск его в хеш-таблице.

Answer 3

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

Answer 4

каноническим примером является Quicksort, который имеет худшее время O (n ^ 2), в то время как Heapsort - O (n logn). однако на практике быстрая сортировка обычно выполняется быстрее, чем Heapsort. Зачем? две причины:

• каждая итерация в быстрой сортировке намного проще, чем в Heapsort. Более того, его легко оптимизировать с помощью простых стратегий кэширования.

• наихудший случай очень трудно ударить.

Но ИМХО, это ни в коем случае не означает, что «большой О провал» первый фактор (время итерации) легко включить в ваши оценки. в конце концов, большие числа O должны быть умножены на это почти постоянное значение.

второй фактор исчезает, если вместо средних значений вы получаете амортизированные цифры. Их может быть сложнее оценить, но расскажите более полную историю

Answer 5

Big-O описывает эффективность / сложность алгоритма и не обязательно время выполнения реализации данного блока кода. Это не значит, что Big-O терпит неудачу. Это просто означает, что он не предназначен для прогнозирования времени работы.

Проверьте ответ на на этот вопрос , чтобы получить большое определение Big-O.

Answer 6

Одна область, где Big O терпит неудачу, это шаблоны доступа к памяти. Big O считает только те операции, которые необходимо выполнить - он не может отследить, приводит ли алгоритм к большему количеству пропусков кэша или данных, которые необходимо перенести с диска. Для малых N эти эффекты обычно будут доминировать. Например, линейный поиск по массиву из 100 целых чисел, вероятно, превзойдет поиск по двоичному дереву из 100 целых чисел из-за обращений к памяти, хотя двоичное дерево, скорее всего, потребует меньше операций. Каждый узел дерева будет приводить к потере кэша, тогда как линейный поиск будет чаще всего попадать в кэш для каждого поиска.

Answer 7

1. Для большинства алгоритмов есть «средний случай» и «наихудший случай». Если ваши данные обычно попадают в сценарий «наихудшего случая», возможно, что другой алгоритм, хотя теоретически менее эффективный в среднем случае, может оказаться более эффективным для ваших данных.

2. Некоторые алгоритмы также имеют лучшие случаи, когда ваши данные могут использовать в своих интересах. Например, некоторые алгоритмы сортировки имеют ужасную теоретическую эффективность, но на самом деле они очень быстрые, если данные уже отсортированы (или почти). Другой алгоритм, хотя теоретически быстрее в общем случае, может не использовать тот факт, что данные уже отсортированы и на практике работают хуже.

3. Для очень маленьких наборов данных иногда алгоритм, который имеет лучшую теоретическую эффективность, может на самом деле быть менее эффективным из-за большого значения "k".

Answer 8

Один пример (который я не являюсь экспертом) заключается в том, что симплексные алгоритмы для линейного программирования имеют экспоненциальную сложность наихудшего случая на произвольных входах, даже если они хорошо работают на практике. Интересным решением этой проблемы является рассмотрение «сглаженной сложности», которая сочетает в себе производительность в худшем и среднем случае, рассматривая небольшие случайные возмущения произвольных входов.

Spielman and Teng (2004) смогли показать, что симплекс-алгоритм теневых вершин имеет полиномиальную сглаженную сложность.

Answer 9

Большой O не говорит, например, этот алгоритм A работает быстрее, чем алгоритм B. Он может сказать, что время или пространство, используемое алгоритмом A, растет с другой скоростью, чем алгоритм B, когда увеличивается входной сигнал. Тем не менее, для любого конкретного размера ввода, большие обозначения O ничего не говорят о производительности одного алгоритма относительно другого.

Например, A может быть медленнее для каждой операции, но иметь большее значение big-O, чем B. B более эффективен для меньшего ввода, но если размер данных увеличивается, будет некоторая точка отсечения, где A становится быстрее , Big-O само по себе ничего не говорит о том, где находится эта точка отсечения.

Answer 10

Это в некоторой степени зависит от того, что измеряет Big-O - в худшем случае он обычно «провалится», поскольку производительность во время выполнения будет намного лучше, чем предполагает Big-O. Если это средний случай, то это может быть намного хуже.

Нотация Big-O обычно «не срабатывает», если входные данные алгоритма содержат некоторую предварительную информацию. Зачастую нотация Big-O относится к сложности наихудшего случая - что часто случается, если данные либо полностью случайные, либо совершенно неслучайные.

Например, если вы подаете данные в профилируемый алгоритм, а big-o основан на рандомизированных данных, но ваши данные имеют очень четко определенную структуру, ваши результаты могут быть намного быстрее, чем ожидалось. С другой стороны, если вы измеряете среднюю сложность и вводите ужасно рандомизированные данные, алгоритм может работать намного хуже, чем ожидалось.