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

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

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

Answer 2

При расчете медианы группы чисел вы можете использовать алгоритм, очень похожий на быструю сортировку. Вы делите число на части, и все более крупные переходят в одну сторону, а все более мелкие переходят в другую. Затем вы отбрасываете одну сторону и рекурсивно вычисляете медиану большей стороны. Это берет O (n ^ 2) в худшем случае, но довольно быстро (O (n) с низкой постоянной) в среднем случае.

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

Answer 3

Хорошо, рассмотрим решение проблемы коммивояжера. Идеальным решением ONLY является проверка всех возможных маршрутов. Однако это становится невозможным с нашими аппаратными средствами и временными рамками, поскольку N увеличивается. Итак, мы подумали о многих эвристиках.

Что подводит нас к ответу на ваш вопрос. Эвристика (хуже) лучше, чем грубая сила для NP-полных задач. Это описывает ситуацию, в которой «Хуже лучше» всегда верно.

Answer 4

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

Answer 5

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

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

Но есть несколько причин, по которым я не могу этого сделать:

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

2. Было бы трудно создать эффективный алгоритм для запоминания этого огромного проблемного пространства.

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

Я уверен, что вы можете думать о других проблемах.

На самом деле, такого рода компромисс между временем и пространством невероятно распространен на практике. В идеале все данные должны храниться в кеше L1, но из-за ограничений по размеру вам всегда нужно поместить некоторые данные на диск или (ужас!) Ленту. Развитие технологий уменьшает некоторые из этих компромиссов, но, как я уже говорил выше, существуют ограничения.

---

В ответ на комментарий Я.Ф. Себастьяна:

Предположим, что вместо универсального репозитория заметок мы рассмотрим факториальный репозиторий. И он не будет содержать результаты для всех возможных входов. Скорее, оно будет ограничено результатами от 1 до N!. Теперь легко увидеть, что любой компьютер, который делал факториалы, выиграл бы от просмотра результата, а не от вычисления. Даже для вычисления (N+1)! поиск будет огромным выигрышем, поскольку этот расчет уменьшится до N!(N+1).

Теперь, чтобы сделать этот «лучший» алгоритм хуже, мы можем либо увеличить N, либо увеличить количество компьютеров, использующих репозиторий.

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

Answer 6

Слияние против быстрой сортировки

Быстрая сортировка имеет среднюю сложность по времени O ( n log n ). Он может сортировать массивы на месте, то есть сложность пространства O (1).

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

Из-за наихудшего случая сложность быстрой сортировки по времени равна Θ (n ^ 2) (т. Е. Все элементы находятся на одной стороне каждой оси), а наихудший случай слияния - O ( n log *) 1023 * n ), mergesort является выбором по умолчанию для разработчиков библиотек.

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

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

Answer 7

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

Это облегчает проектирование, производство и обслуживание.

Answer 8

Существует алгоритм O (n) для выбора k-го по величине элемента из несортированного набора, но он редко используется вместо сортировки, что, конечно, O (n logn).

Answer 9

Сортировка вставкой, несмотря на сложность O (n ² ), быстрее для небольших коллекций (n <10), чем любой другой алгоритм сортировки. Это потому, что вложенный цикл маленький и выполняется быстро. Многие библиотеки (включая STL), в которых реализован метод сортировки, фактически используют его для небольших подмножеств данных, чтобы ускорить процесс. </p>

Answer 10

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