Хуже лучше. Есть ли пример? - PullRequest
Новая
       55

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

47 голосов
/ 23 января 2009

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

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

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

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

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

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

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

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

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

Связанный:

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

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

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

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

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

Ответы [ 23 ]

1 голос
/ 29 января 2009

Интеграция с Монте-Карло уже была предложена, но более конкретный пример - ценообразование Монте-Карло в сфере финансов. Здесь метод намного проще для кодирования и может делать больше вещей, чем некоторые другие, НО это намного медленнее, чем, скажем, конечная разница.

20-мерные конечно-разностные алгоритмы нецелесообразны, но легко настроить 20-мерное ценообразование.

0 голосов
/ 12 июля 2013 
Quick-sort has worst case time complexity of O(N^2)! 
It is considered better than other sorting algorithms 
like mergesort heapsort etc. which have O(N log n) time complexity 
in the worst case.
The reason may be the 
1.in place sorting 
2.stability, 
3.very less amount of code involved.
0 голосов
/ 31 мая 2010

Итеративное углубление

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

Страница:
...