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

Ответ 1

алгоритм Coppersmith-Winograd для умножения квадратной матрицы. Его временная сложность равна O (n ^2.376) по сравнению с O (n ³) наивного алгоритма умножения или против O (n ^2.807) для алгоритм Strassen.

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

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

Ответ 7

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

Ответ 8

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

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

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

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

За исключением кипячения океанов, то, что считается "всеми практическими ситуациями", часто является переменной, зависящей от времени.

Ответ 9

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

EDIT: (JFS)

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

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

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

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

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

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

[3]:

Ответ 10

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

Ответ 11

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

Ответ 12

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

Ответ 13

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

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

Ответ 14

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

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

Ответ 15

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 16

Mergesort и Quicksort

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

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

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

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

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

Ответ 17

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

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

Ответ 18

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

Ответ 19

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

Ответ 20

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

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

Ответ 21

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

Ответ 22

Есть много примеров.

Например:

1. У Y-fast-trie сложное время логлогии для преемника/предшественника, но у него большие константы, так что BST (то есть logn) лучше.

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

3. То же, что 2, но для поиска MSB регистра.

4. Fusion tree имеет сложность запроса O (logn/loglogu), но с ОГРОМНЫМИ константами (константами, которые намного больше, чем во всех предыдущих примерах), и BST может достичь того же в logn. Так что BST ВСЕГДА лучше (если у вас нет бесконечного количества данных, что невозможно).

Ответ 23

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

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

Ответ 24

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.