Хуже лучше. Существует ли пример?

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

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

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

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

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

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

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

Сортировка с объединением по сравнению с быстрой сортировкой Quicksort

имеет среднюю временную сложность O ( журнал n n). Это может отсортировать массивы на месте, т.е. сложность пространства O (1).

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

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

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

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

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

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

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

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

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

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

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

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

В ответ на J.F. Комментарий Sebastian:

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

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

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

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

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

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

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

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

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

Регулярное выражение, Соответствующее, Может Быть Простым И Быстрым (но является медленным в Java, Perl, PHP, Python, Ruby...) :

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

Механизмы Регулярного выражения :

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

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

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

[3]:

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

, По-видимому, размер набора был 641K.

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

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

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

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

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

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

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

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

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

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

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

Существует много примеров.

, Например:

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

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

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

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

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

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

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