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

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

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

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

Примеры выделяются из ответов:

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

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

  • Отслеживание в обратном порядке regex механизмы - экспоненциал худшего случая по сравнению с O (N) Thompson NFA - базирующиеся механизмы.

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

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


Похожие страницы:

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

  • Принципы проектирования Python:

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

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

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

47
задан 10 revs, 4 users 99% 31 May 2010 в 03:55
поделиться

19 ответов

Coppersmith†“алгоритм Винограда для умножения квадратной матрицы. Его временная сложность является O (n <глоток> 2.376 ) по сравнению с O (n <глоток> 3 ) наивного алгоритма умножения или по сравнению с O (n <глоток> 2.807 ) для алгоритм Штрассена .

От статьи Википедии:

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

12
ответ дан jfs 26 November 2019 в 19:11
поделиться

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

35
ответ дан Svante 26 November 2019 в 19:11
поделиться

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

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

1
ответ дан Simon P 26 November 2019 в 19:11
поделиться

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

2
ответ дан vava 26 November 2019 в 19:11
поделиться

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

2
ответ дан Rafał Dowgird 26 November 2019 в 19:11
поделиться

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

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

2
ответ дан Josh Smeaton 26 November 2019 в 19:11
поделиться

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

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

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

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

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

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

3
ответ дан jamesh 26 November 2019 в 19:11
поделиться

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

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

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

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

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

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

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

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

<час>

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

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

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

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

4
ответ дан Jon Ericson 26 November 2019 в 19:11
поделиться

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

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

4
ответ дан Sasha 26 November 2019 в 19:11
поделиться

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

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

4
ответ дан Robert Gould 26 November 2019 в 19:11
поделиться

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

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

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

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

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

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

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

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

[3]:

5
ответ дан j_random_hacker 26 November 2019 в 19:11
поделиться

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

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

<час>

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

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

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

8
ответ дан Pete Kirkham 26 November 2019 в 19:11
поделиться

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

9
ответ дан Dave Ray 26 November 2019 в 19:11
поделиться

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

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

10
ответ дан Matt J 26 November 2019 в 19:11
поделиться

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

14
ответ дан Dour High Arch 26 November 2019 в 19:11
поделиться

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

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

15
ответ дан Robert Gould 26 November 2019 в 19:11
поделиться

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

4
ответ дан Nick Johnson 26 November 2019 в 19:11
поделиться

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

29
ответ дан 0x499602D2 26 November 2019 в 19:11
поделиться

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

, Например:

  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 ВСЕГДА лучше (если у Вас на самом деле нет бесконечного объема данных, который невозможен).

1
ответ дан 26 November 2019 в 19:11
поделиться
Другие вопросы по тегам:

Похожие вопросы: