Существуют ли реальные алгоритмы, которые значительно превосходят классы ниже? [закрыто]

39

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

Есть ли примеры алгоритмов, которые значительно превосходят те, что в классе ниже? Например, O (n) быстрее, чем O (1), или O (n 2 ) быстрее, чем O (n).

Математически это можно продемонстрировать для функции с асимптотическими верхними границами, когда вы игнорируете постоянные множители, но существуют ли такие алгоритмы в дикой природе? И где я могу найти примеры из них? В каких ситуациях они используются?

KyleWpppd
источник
15
Даже для «больших» алгоритмов меньший не обязательно лучше. Например, исключение по Гауссу - это O (n ^ 3), но есть алгоритмы, которые могут сделать это за O (n ^ 2), но коэффициент для квадратичного алгоритма времени настолько велик, что люди просто идут с O (n ^ 3) один.
Блэкджек,
11
Вы должны добавить «... для реальных проблем» или что-то подобное, чтобы сделать этот вопрос разумным. В противном случае вам нужно только сделать nдостаточно большим, чтобы компенсировать константу (которая является точкой обозначения big-O).
starblue
8
Не принимайте обозначение Big-O для скорости.
Кодизм
16
Смысл нотации big-O не в том, чтобы рассказать вам, как быстро работает алгоритм, а в том, насколько хорошо он масштабируется.
BlueRaja - Дэнни Пфлюгофт
4
Я удивлен, что никто не упомянул алгоритм Simplex для решения LP. Он имеет экспоненциальный наихудший случай с ожидаемым линейным временем выполнения. На практике это довольно быстро. Тривиально построить задачу, которая также демонстрирует наихудший вариант выполнения. Кроме того, он интенсивно используется.
Ccoakley

Ответы:

45

Поиск в очень маленьких, фиксированных таблицах данных. Оптимизированная хеш-таблица может иметь значение O (1) и все же медленнее, чем бинарный поиск или даже линейный поиск из-за стоимости вычисления хеш-функции.

Лорен Печтель
источник
14
Точнее, поиск по хеш-таблице - это O (m), где m - размер ключа. Вы можете вызвать это O (1), только если размер ключа постоянен. Кроме того, обычно это амортизируется - иначе таблица не может расти / уменьшаться. Тернарные деревья могут часто разбивать хеш-таблицы для поиска строк в тех случаях, когда строки довольно часто не обнаруживаются - при поиске троичного дерева часто обнаруживается, что ключа нет, но при этом проверяется первый или два символа строки, где хэш-версия еще не рассчитала хэш.
Steve314
2
Мне нравится ответ Лорен Печтель и первый комментарий Steve314. Я действительно видел, как это произошло. Если вы создаете Java-класс, который имеет метод hashcode (), который занимает слишком много времени, чтобы вернуть значение хеша (и не может / не может его кэшировать), то используйте экземпляры такого класса в коллекции хеш-типа (например, HashSet) сделает эту коллекцию ALOT более медленной, чем коллекция типа массива (например, ArrayList).
Shivan Dragon
1
@ Steve314: почему вы полагаете, что хеш-функции равны O (m), где m - размер ключа? Хэш-функции могут быть O (1), даже если вы имеете дело со строками (или другим сложным типом). Нет слишком большого значения, чтобы поместить его в формальное определение, чем простое понимание хэш-функции может значительно изменить сложность, если для вашего ввода выбрана неправильная структура данных (хеш-таблица) (размер ключа непредсказуем).
Кодизм
1
@ Steve314: Обратите внимание, что я сказал фиксированные таблицы данных. Они не растут. Кроме того, производительность O (1) можно получить только из хеш-таблицы, если вы можете оптимизировать ключ, чтобы избежать коллизий.
Лорен Печтел
1
@Loren - строго говоря, если таблица имеет фиксированный размер, есть постоянное максимальное количество времени, которое вы можете потратить на поиск свободного места. То есть, самое большее, вам может понадобиться проверить n-1 уже заполненных слотов, где n - постоянный размер таблицы. Таким образом, хеш-таблица с фиксированным размером действительно равна O (1), без необходимости амортизированного анализа. Это не означает, что вы не заботитесь о том, что доступы становятся медленнее по мере заполнения таблицы - только то, что это не то, что выражает большой O.
Steve314
25

Матричное умножение. Наивный алгоритм O (n ^ 3) часто используется на практике быстрее, чем алгоритм Штрассена O (n ^ 2.8) для матриц малого размера; и Штрассена используется вместо алгоритма O (n ^ 2.3) Копперсмита – Винограда для больших матриц.

Питер Тейлор
источник
2
Медник-Виноград НИКОГДА не используется. Реализация этого была бы ужасной задачей сама по себе, и константа настолько плоха, что была бы невозможна даже для современных научных матриц-задач.
tskuzzy
24

Простым примером является разница между различными алгоритмами сортировки. Mergesort, Heapsort и некоторые другие являются O (n log n) . Быстрая сортировка - наихудший случай O (n ^ 2) . Но часто быстрая сортировка выполняется быстрее, и фактически она работает в среднем как O (n log n) . Более подробная информация .

Другим примером является генерация одного числа Фибоначчи. Итерационный алгоритм O (n) , в то время как алгоритм на основе матрицы O (log n) . Тем не менее, для первой пары тысяч чисел Фибоначчи итерационный алгоритм, вероятно, быстрее. Это также зависит от реализации, конечно!

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

оборота мольф
источник
Это отличное объяснение Big-O, но не решает сути вопроса, который для конкретных случаев, когда алгоритм O (n) будет быстрее, чем O (1).
KyleWpppd
Фибоначчи номер один немного выключен. Размер вывода является экспоненциальным по размеру ввода, поэтому это разница между O (lg n * e ^ n) и O (lg lg n * e ^ n).
Питер Тейлор
Приложение: в лучшем случае. Алгоритм на основе матрицы выполняет умножение с числами порядка 1,5 ^ n, поэтому O (lg lg n * ne ^ n) может быть наилучшим доказуемым доказательством.
Питер Тейлор
1
Быстрая сортировка обычно описывается как ожидаемая производительность O (n log n) в любом случае - наихудший случай довольно маловероятен для случайных входов, а включение некоторой случайности в предварительный проход или в выбор поворота означает, что наихудший случай в целом очень маловероятен для значительных входных размеров. Худший случай менее актуален, чем тот факт, что быстрая сортировка (1) очень проста и (2) очень удобна для кэша, что приводит к значительно лучшим постоянным коэффициентам, чем во многих других алгоритмах сортировки.
Steve314
(2) - это как раз то внешнее соображение, которое необходимо учитывать при оценке производительности big-O. С точки зрения алгоритма, Mergesort всегда должен превосходить Quicksort, но использование ресурсов и локальность кэша обычно меняют их реальную производительность.
Дэн Лайонс
18

Примечание: Пожалуйста, прочитайте комментарии @ back2dos ниже и других гуру, так как они на самом деле более полезны, чем то, что я написал - спасибо всем авторам.

Я думаю, что из приведенной ниже таблицы (взятой из: обозначение Big O , поиск «Пессимистическая природа алгоритмов:») вы можете видеть, что O (log n) не всегда лучше, чем, скажем, O (n). Итак, я думаю, ваш аргумент верен.

Pic-1

Emmad Kareem
источник
6
Вопрос хотел конкретные примеры реальных алгоритмов. Это не имеет, как оно есть.
Меган Уокер
19
Вы не можете видеть ничего на этом графике, это ответило бы на вопрос. Это вводит в заблуждение. Этот график только участки функции y = 1, y = log xи так далее , и пересечение y = 1и y = xна самом деле точка (1,1). Если бы это действительно было правильно, чем это говорило бы вам, то алгоритмы более высокой сложности могут быть быстрее для 0 - 2 записей, что людям вряд ли понадобится. То, что граф полностью не учитывает (и из-за чего возникает ощутимая разница в производительности), является постоянными факторами.
back2dos
@ Сэмюэл Уокер, спасибо за комментарий. Предоставленная ссылка (Ссылка-1) содержит несколько примеров алгоритмов для каждой категории.
NoChance
5
@ back2dos: сам график не отвечает на вопрос, но может использоваться для ответа на него. Форма каждой отображаемой функции одинакова для любого масштаба и постоянного коэффициента. При этом график показывает, что при данной комбинации функций существует диапазон входов, для которых один меньше, и диапазон входов, для которых другой.
Ян Худек
2
@dan_waterworth, вы правы, я согласен с этим и удалю этот комментарий. Тем не менее, ответ неверен или вводит в заблуждение в двух отношениях: 1) Весь смысл Big-O в том, что он дает верхнюю границу сложности; это имеет смысл только для больших n, потому что мы явно выбрасываем меньшие члены, которые перегружаются наибольшим с ростом n. 2) Суть вопроса состоит в том, чтобы найти примеры двух алгоритмов, в которых тот, у которого более высокая граница Big-O, превосходит тот, у которого нижняя граница. Этот ответ терпит неудачу, потому что он не дает таких примеров.
Калеб
11

Для практических ценностей n, да. Это очень часто встречается в теории CS. Часто существует сложный алгоритм, который технически имеет лучшую производительность, но постоянные факторы настолько велики, что делают его непрактичным.

Однажды мой профессор вычислительной геометрии описал алгоритм триангуляции многоугольника за линейное время, но он закончил словами «очень сложно. Я не думаю, что кто-то на самом деле его реализовал» (!!).

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

оборота Гейб Моутарт
источник
Это быстрее для огромных графов порядка 100 000 или около того вершин.
tskuzzy
Кучи Фибоначчи были моей первой (фактически второй) мыслью.
Конрад Рудольф
10

Сравните вставку в связанный список и вставку в массив с изменяемым размером.

Объем данных должен быть достаточно большим, чтобы вставка связанного списка O (1) была полезной.

Связанный список имеет дополнительные накладные расходы для следующих указателей и разыменований. Массив с изменяемым размером должен копировать данные вокруг. Это копирование O (n), но на практике очень быстро.

Уинстон Эверт
источник
1
Масса с изменяемым размером удваивается по размеру при каждом заполнении, поэтому средняя стоимость изменения размера на вставку составляет O (1).
Кевин Клайн
2
@kevincline, да, но O (n) происходит от необходимости перемещать все элементы после точки вставки вперед. Выделение амортизируется O (1) раз. Моя точка зрения заключается в том, что это движение все еще очень быстрое, поэтому на практике обычно бьет связанные списки.
Уинстон Эверт
Причина, по которой смежные массивы являются такими быстрыми по сравнению со связанными списками, связана с кэшированием процессора. Обход связанного списка приведет к отсутствию кэша для каждого элемента. Чтобы получить лучшее из обоих миров, вы должны использовать развернутый связанный список .
dan_waterworth
Изменяемые размеры массивов не всегда копируются. Это зависит от того, на чем он работает и есть ли что-то на пути. То же самое для удвоения размера, конкретной реализации. Перевернуть, перевернуть вещь, хотя это проблема. Связанные списки, как правило, лучше всего подходят для очередей неизвестного размера, хотя ротационные буферы дают очереди за свои деньги. В других случаях связанные списки полезны, потому что выделение или расширение просто не позволяют постоянно иметь непрерывные данные, поэтому вам все равно понадобится указатель.
jgmjgm
@jgmjgm, если вы вставляете в середину массива с изменяемым размером, то после этого абсолютно точно копируются элементы.
Уинстон Эверт
8

Обозначение Big-Oh используется для описания скорости роста функции, поэтому возможно, что алгоритм O (1) будет быстрее, но только до определенной точки (постоянный коэффициент).

Общие обозначения:

O (1) - Количество итераций (иногда вы можете называть это временем пользователя, потраченным функцией) не зависит от размера ввода и фактически является постоянным.

O (n) - количество итераций растет линейно пропорционально размеру ввода. Значение: если алгоритм повторяет любые входные данные N, 2 * N раз, он все равно считается O (n).

O (n ^ 2) (квадратичный) - количество итераций равно квадрату входного размера.

Ям Маркович
источник
2
Чтобы добавить пример к отличному ответу: метод O (1) может занять 37 лет на вызов, тогда как метод O (n) может занять 16 * n микросекунд на вызов. Что быстрее?
Каз Драгон
16
Я совершенно не вижу, как это отвечает на вопрос.
Авакар
7
Я понимаю биг-о. Это не относится к актуальному вопросу, а именно к конкретным примерам функций, где алгоритмы с более низким big-O превосходят алгоритмы с более высоким big-O.
KyleWpppd
Когда вы ставите вопрос в форме «Есть ли примеры ...», кто-то неизбежно собирается ответить «Да». не давая никаких.
Ракслице
1
@rakslice: Может быть и так. Однако этот сайт требует объяснения (или, еще лучше, доказательства) любых ваших заявлений. Теперь лучший способ доказать, что такие примеры есть, привести один;)
back2dos
6

Библиотеки Regex, как правило, реализуются для возврата, который имеет экспоненциальное время в худшем случае, а не генерацию DFA, которая имеет сложность O(nm).

Наивное обратное отслеживание может быть более эффективным, когда ввод остается на быстром пути или терпит неудачу без необходимости чрезмерного возврата.

(Хотя это решение основано не только на производительности, но и на обратных ссылках.)

dan_waterworth
источник
Я думаю, что это также отчасти исторически - алгоритм превращения регулярного выражения в DFA был запатентован, когда разрабатывались некоторые из более ранних инструментов (я полагаю, sed и grep). Конечно, я слышал это от своего профессора по компиляции, который не был полностью уверен, так что это аккаунт из третьих рук.
Тихон Джелвис
5

O(1)Алгоритм:

def constant_time_algorithm
  one_million = 1000 * 1000
  sleep(one_million) # seconds
end

O(n)Алгоритм:

def linear_time_algorithm(n)
  sleep(n) # seconds
end

Очевидно, что для любого значения nгде n < one_million, то O(n)алгоритм в приведенном примере будет быстрее , чем O(1)алгоритм.

Хотя этот пример немного шутливый, он по духу эквивалентен следующему примеру:

def constant_time_algorithm
  do_a_truckload_of_work_that_takes_forever_and_a_day
end

def linear_time_algorithm(n)
  i = 0
  while i < n
    i += 1
    do_a_minute_amount_of_work_that_takes_nanoseconds
  end
end

Вы должны знать константы и коэффициенты в своем Oвыражении, и вы должны знать ожидаемый диапазон n, чтобы априори определить, какой алгоритм будет быстрее.

В противном случае вы должны сравнить два алгоритма со значениями nв ожидаемом диапазоне, чтобы определить апостериори, какой алгоритм оказался быстрее.

yfeldblum
источник
4

Сортировка:

Сортировка вставкой O (n ^ 2), но превосходит другие алгоритмы сортировки O (n * log (n)) для небольшого числа элементов.

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

См. Timsort о текущей реализации по умолчанию сортировки Python и Java 7, использующей эту технику.

Olivers
источник
3

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

Это должно быть примером, к которому он может относиться.

user1249
источник
Разве указанные сложности по быстрой сортировке и пузырьковой сортировке не предполагают O (1) произвольный доступ к памяти? Если это уже не так, не нужно ли пересматривать сложность быстрых сортировок?
Виктор Даль
@ViktorDahl, время доступа к элементу не является частью того, что традиционно измеряется в сложностях алгоритма сортировки, поэтому «O (1)» не является правильным выбором слов здесь. Вместо этого используйте «постоянное время». PHK некоторое время назад написал статью об алгоритмах сортировки, зная, что некоторые элементы дороже извлекать, чем другие (виртуальная память) - queue.acm.org/detail.cfm?id=1814327 - вам может быть интересно.
Теперь я вижу свою ошибку. Обычно измеряется количество сравнений, и, конечно, они не зависят от скорости носителя. Также спасибо за ссылку.
Виктор Даль
3

Часто более продвинутые алгоритмы предполагают определенную (дорогую) настройку. Если вам нужно запустить его только один раз, вам лучше воспользоваться методом грубой силы.

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

Сортировка обойдется вам в N log (N), а хеш-таблица будет стоить как минимум N. Теперь, если вы собираетесь выполнять сотни или тысячи поисков, это все еще амортизированная экономия. Но если вам нужно выполнить только один или два поиска, возможно, имеет смысл просто выполнить линейный поиск и сохранить стоимость запуска.

оборота Мэтью Скотен
источник
1

Расшифровка часто 0 (1). Например, пространство ключей для DES равно 2 ^ 56, поэтому расшифровка любого сообщения является операцией с постоянным временем. Просто у вас есть коэффициент 2 ^ 56, так что это действительно большая константа.

Захари К
источник
Разве дешифрование сообщения не является O ( n ), где n пропорционально размеру сообщения? Пока у вас есть правильный ключ, размер ключа даже не учитывается; некоторые алгоритмы имеют минимальные или никакие процессы настройки / расширения ключа (DES, RSA - обратите внимание, что генерация ключа все еще может быть сложной задачей, но это не имеет ничего общего с расширением ключа), тогда как другие являются чрезвычайно сложными (приходит на ум Blowfish), но как только это будет сделано, время выполнения фактической работы будет пропорционально размеру сообщения, следовательно, O (n).
CVn
Вы, вероятно, имеете в виду криптоанализ, а не дешифрование?
оставил около
3
Ну, да, есть множество вещей, которые вы можете считать постоянными и объявить алгоритм равным O (1). [сортировка подразумевает, что для сравнения элементов требуется, например, постоянное количество времени, или любая математика с небигнумными числами]
Random832
1

Различные реализации наборов возникают в моей памяти. Одним из наиболее наивных является реализация его по вектору, что означает, removeчто containsи, следовательно, также addвсе принимают O (N).
Альтернативой является реализация этого через некоторый хеш общего назначения, который отображает входные хеш-значения во входные значения. Такой набор выполняет реализацию с O (1) для add, containsи remove.

Если мы предположим, что N около 10 или около того, то первая реализация, вероятно, быстрее. Чтобы найти элемент, достаточно сравнить 10 значений с одним.
Другая реализация должна запустить все виды умных преобразований, которые могут быть намного дороже, чем сделать 10 сравнений. Несмотря на все накладные расходы, вы можете даже иметь ошибки в кэше, и тогда действительно не имеет значения, насколько быстро ваше решение теоретически.

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

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

back2dos
источник
1

Да, для достаточно малого N. Всегда будет N, выше которого у вас всегда будет порядок O (1) <O (lg N) <O (N) <O (N log N) <O (N ^ c ) <O (c ^ N) (где O (1) <O (lg N) означает, что при алгоритме O (1) потребуется меньше операций, когда N достаточно велико и c является некоторой фиксированной константой, которая больше 1 ).

Скажем, конкретный алгоритм O (1) требует ровно f (N) = 10 ^ 100 (гугол) операций, а алгоритм O (N) - ровно g (N) = 2 N + 5 операций. Алгоритм O (N) будет давать большую производительность до тех пор, пока N не станет примерно гуголом (фактически, когда N> (10 ^ 100 - 5) / 2), поэтому, если вы ожидаете, что N будет находиться в диапазоне от 1000 до миллиарда, вы будет страдать от серьезного штрафа с использованием алгоритма O (1).

Или для реалистичного сравнения, скажем, вы умножаете n-значные числа вместе. Алгоритм Карацуба составляет не более 3 п ^ (LG 3) операция (то есть примерно O (N ^ 1,585)) , тогда как алгоритм Шёнхаг-Штрассен является O (N журнал N журнал журнал N) , который представляет собой быстрый порядок , но цитировать википедия:

На практике алгоритм Шёнхаге – Штрассена начинает опережать более старые методы, такие как умножение Карацубы и Тоом – Кука, для чисел от 2 ^ 2 ^ 15 до 2 ^ 2 ^ 17 (от 10 000 до 40 000 десятичных цифр). [4] [5] [6 ]

Так что, если вы умножаете 500-значные числа вместе, не имеет смысла использовать алгоритм, который «быстрее» при больших аргументах O.

РЕДАКТИРОВАТЬ: Вы можете найти определение f (N) по сравнению g (N), взяв предел N-> бесконечность f (N) / g (N). Если предел равен 0, то f (N) <g (N), если предел равен бесконечности, то f (N)> g (N), а если предел - это некоторая другая постоянная, то f (N) ~ g (N) с точки зрения большой нотации.

оборота д-р джимбоб
источник
1

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

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

comingstorm
источник
0

Алгоритм Укконена для построения суффиксных попыток - O (n log n). Преимущество состоит в том, что он «онлайн», то есть вы можете постепенно добавлять больше текста.

В последнее время другие более сложные алгоритмы утверждают, что они быстрее на практике, в основном потому, что их доступ к памяти имеет более высокую локальность, что улучшает использование кэша процессора и позволяет избежать остановок конвейера ЦП. Смотрите, например, этот опрос , в котором утверждается, что 70-80% времени обработки тратится на ожидание памяти, и этот документ описывает алгоритм «wotd».

Суффиксные попытки важны в генетике (для сопоставления последовательностей генов) и, что несколько менее важно, в реализации словарей Scrabble.

Эд Стауб
источник
0

Всегда есть любой четко определенной задачи самый быстрый и короткий алгоритм . Это только чисто теоретически (асимптотически) самый быстрый алгоритм.

Учитывая любое описание проблемы P и экземпляр для этой задачи I , он перебирает все возможные алгоритмы и доказательства Pr , проверяя для каждой такой пары ли Pr является допустимым доказательством того, что является асимптотически быстрый алгоритм для P . Если он находит такое доказательство, он затем выполняет A на I .

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

Алекс тен Бринк
источник
0

Многие языки / платформы используют наивное сопоставление с образцом для сопоставления строк вместо KMP . Мы ищем строку, как Том, Нью-Йорк, а не ababaabababababaababababababab.

Лукаш Мадон
источник