Хуже лучше. Есть ли пример?

Question

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

Приемлемый ответ может быть в форме:

Существуют алгоритмы A и B, которые есть O(N**2) и O(N) время сложность соответственно, но B имеет такую ​​большую константу, что не имеет преимущества перед A для затрат меньше тогда ряд атомов в Вселенная.

Примеры основных моментов из ответов:

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

• Наивный алгоритм медианы медиан - наихудший O (N ** 2) против известный алгоритм O (N).

• Двигатели с обратным отслеживанием в регулярных выражениях - экспоненциальный наихудший случай против O (N) двигателей на основе NFA Томпсона.

Все эти примеры используют сценарии наихудшего и среднего сценариев.

Существуют ли примеры, которые не основаны на разнице между наихудшим и средним сценарием?

---

Связанный:

• Повышение "худшего лучше" . (Для целей этого вопроса фраза «Хуже лучше» используется в более узком (а именно - алгоритмическая сложность времени) смысле, чем в статье)

• Философия дизайна Python :

  Группа ABC стремилась к совершенству. Например, они использовали данные на основе дерева алгоритмы структуры, которые были доказаны быть оптимальным для асимптотически больших коллекции (но были не так хороши для небольшие коллекции).

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

• Алгоритм Копперсмита-Винограда для умножения квадратной матрицы является хорошим примером (это самый быстрый (2008 год), но он уступает худшим алгоритмам). Кто-нибудь еще? Из статьи в Википедии: «На практике она не используется, поскольку она дает преимущество только для матриц, настолько больших, что их невозможно обработать современным оборудованием (Robinson 2005)».

Answer 1

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

Answer 2

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

Answer 3

«Хуже лучше» можно увидеть и в языках, например, идеи Perl, Python, Ruby, Php даже C # или Java, или любой другой язык, который не является ассемблером или C (C ++ может подходить здесь или нет) .

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

Answer 4

Алгоритм Копперсмита – Винограда для умножения квадратной матрицы. Его временная сложность составляет O (n ^2,337 ) против O (n ³ ) алгоритма простого умножения или против O n ^2,807 ) для алгоритм Штрассена .

Из статьи в Википедии:

Однако, в отличие от Штрассена алгоритм, он не используется на практике потому что это только дает преимущество для матриц настолько больших, что они не могут обрабатываться современным оборудованием (Робинсон 2005).

Answer 5

Интеграция по Монте-Карло - это вероятностный метод вычисления определенных интегралов, который не гарантирует возврата правильного ответа. Тем не менее, в реальных ситуациях он дает точный ответ гораздо быстрее, чем достоверно правильные методы.

Answer 6

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

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

Answer 7

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

Answer 8

Этот пример был бы ответом, если бы не было компьютеров, способных хранить эти большие коллекции.

Предположительно, размер коллекции был 641K.

---

Когда мы работали в технической вычислительной группе для BAE SYSTEMS, которая занималась структурным и аэродинамическим кодом для различных самолетов, у нас была кодовая база, по крайней мере, 25 лет назад (и треть персонала была там так долго).

Многие из алгоритмов были оптимизированы для производительности на 16-битном мэйнфрейме, а не для масштабируемости. Эти оптимизации были полностью подходящими для оборудования 1970-х годов, но плохо работали на больших наборах данных в 32- и 64-разрядных системах, которые его заменили. Если вы выбираете что-то с худшей масштабируемостью, которая лучше работает на оборудовании, на котором вы сейчас работаете, помните, что это оптимизация, и она может не применяться в будущем. В то время, когда были написаны эти процедуры 1970-х годов, объем данных, который мы ввели в них в 2000-х годах, был непрактичным. К сожалению, попытка извлечь из этих кодов четкий алгоритм, который затем можно было бы реализовать в соответствии с современным оборудованием, не была тривиальной.

Если не считать кипения океанов, то, что считается «всеми практическими ситуациями», часто зависит от времени.

Answer 9

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

РЕДАКТИРОВАТЬ: (JFS)

Сопоставление регулярных выражений может быть простым и быстрым (но медленным в Java, Perl, PHP, Python, Ruby, ...) :

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

Двигатели регулярных выражений :

Этот метод (DFA) действительно более эффективен, и можно даже адаптировать для захвата и сопоставления без жадности , но он также имеет важные недостатки:

• Взгляды невозможны
• Обратные ссылки также невозможны
• Предварительная компиляция Regex длиннее и занимает больше памяти

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

[3]:

Answer 10

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