Когда запись 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 позволяет вам быть по-настоящему небрежным, скрывая постоянные факторы. Как уже упоминалось в вопросе, использование кучи Фибоначчи является одним из примеров. Кучи Фибоначчи do имеют отличные асимптотические времена выполнения, но на практике факторы констант слишком велики, чтобы их можно было использовать для размеров наборов данных, встречающихся в реальной жизни.

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

Другим похожим примером является алгоритм Копперсмита-Винограда для умножения матриц. В настоящее время это алгоритм с самым быстрым известным асимптотическим временем выполнения для умножения матриц, O (n ^2.376 ). Однако его постоянный коэффициент слишком велик, чтобы быть полезным на практике. Как и Кучи Фибоначчи, он часто используется в качестве строительного блока в других алгоритмах для доказательства теоретических временных ограничений.

Answer 2

1. Маленькое N - И для современных компьютеров 100, вероятно, слишком мало, чтобы волноваться.
2. Скрытые множители - слияние IE и быстрой сортировки.
3. Патологические случаи - Опять слияние с быстрым

Answer 3

Одна широкая область, где сбой записи Big-Oh, - это когда объем данных превышает доступный объем ОЗУ.

Используя сортировку в качестве примера, количество времени, которое требуется для сортировки, не зависит от количества сравнений или обменов (из которых O (n log n) и O (n), соответственно, в оптимальном случае соответственно). ). Количество времени зависит от количества операций на диске: запись блока и чтение блока.

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

• Количество элементов, Н;
• Объем памяти (ОЗУ), М (количество элементов, которые могут находиться в памяти); и
• Размер блока диска, B (количество элементов в блоке).

Заметно отсутствует количество дискового пространства; это рассматривается как если бы оно было бесконечным. Типичным дополнительным предположением является то, что M> B ² .

Продолжая пример сортировки, вы обычно предпочитаете сортировку слиянием в случае ввода / вывода: разделите элементы на куски размером θ (M) и отсортируйте их в памяти (скажем, быстрой сортировкой). Затем объедините θ (M / B) из них, считав первый блок из каждого куска в память, поместите все элементы в кучу и многократно выбирайте наименьший элемент, пока не выберете B из них. Запишите этот новый блок слияния и продолжайте. Если вы когда-нибудь исчерпали один из блоков, которые вы прочитали, в память, прочитайте новый блок из того же блока и поместите его в кучу.

(все выражения должны читаться как большие θ). Вы формируете N / M отсортированные куски, которые затем объединяются. Вы объединяете журнал (базовый M / B) N / M раз; каждый раз, когда вы читаете и записываете все блоки N / B, то есть у вас уходит время N / B * (логарифм M / B из N / M).

Вы можете проанализировать алгоритмы сортировки в памяти (соответствующим образом модифицированные, чтобы включить чтение блоков и запись блоков) и увидеть, что они намного менее эффективны, чем сортировка слиянием, которую я представил.

Это знание любезно предоставлено моими курсами по алгоритмам ввода / вывода Арге и Бродалом (http://daimi.au.dk/~large/ioS08/);). Я также проводил эксперименты, подтверждающие теорию: сортировка кучи занимает «почти бесконечное» время, как только вы превышаете память. сортировка становится невыносимо медленной, сортировка слиянием едва терпимо медленной, эффективная сортировка ввода / вывода работает хорошо (лучший из множества).

Answer 4

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

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

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

Answer 5

Этот вопрос похож на вопрос: «Когда IQ человека терпит неудачу на практике?» Понятно, что высокий IQ не означает, что вы будете успешны в жизни, а низкий IQ не означает, что вы погибнете. Тем не менее, мы измеряем IQ как средство оценки потенциала, даже если он не является абсолютным.

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

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

Answer 6

Когда ваши данные не соответствуют модели , нотация big-o все равно будет работать, но вы увидите наложение в лучших и худших сценариях.

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

Очевидно, как я забыл, также , когда N мало :)

Answer 7

Роберт Седжвик рассказывает о недостатках нотации big-O в своем курсе Coursera «Анализ алгоритмов». Он называет особенно вопиющие примеры галактические алгоритмы , потому что, хотя они могут иметь более высокий класс сложности, чем их предшественники, для его практического применения потребуются входные данные астрономических размеров.

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

Answer 8

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

Маленькие n случаев очевидны, но не интересны: достаточно быстро, достаточно быстро.

На практике у меня были проблемы с использованием стандартных коллекций в Delphi, Java, C # и Smalltalk с несколькими миллионами объектов. И с меньшими, где доминирующим фактором оказалась хеш-функция или сравнение