Большой O (n logn) не предпочтительнее, чем O (n ^ 2)

Любой пример алгоритмов, когда мы предпочитаем временную сложность Big O (n ^ 2) O (n logn)? Я где-то видел этот вопрос, но не нашел ответа.


algorithm time-complexity space-complexity code-complexity asymptotic-complexity
person Rheatey Bash    schedule 05.02.2016    source источник
comment
Возможный дубликат Есть ли случаи, когда вы бы предпочли более высокий алгоритм большой временной сложности, чем более низкий?   -  person Andrew Elkouri    schedule 05.02.2016
comment
Речь идет об общих причинах выбора более медленных алгоритмов (в данном случае: да, дублировать) или о реальном примере из реальной жизни?   -  person tobias_k    schedule 05.02.2016

Ответы (4)


arrow_upward
7
arrow_downward

Есть несколько причин для выбора алгоритма с более высокой временной сложностью:

  • Скорость: асимптотическая сложность применяется только к значениям n больше некоторого n_0. Кроме того, предполагается, что под ним находится некая машина, которая лишь частично соответствует реальным машинам с несколькими уровнями кеша и ограниченной памятью.
  • Пространство: некоторые алгоритмы требуют больше места, чем другие, и поэтому их невозможно реализовать. Кроме того, это может просто повлиять на скорость на реальной машине. Например, локальность ссылок влияет на попадание или промах в кэш, поэтому быстрая сортировка работает лучше, чем сортировка слиянием.
  • Сложность реализации: в некоторых случаях потеря производительности просто незначительна, но время разработки — нет.
person Ulrich Eckhardt    schedule 05.02.2016

arrow_upward
8
arrow_downward

Для большой проблемы O (n log n) всегда будет лучше O (n ^ 2). Для небольшой задачи постоянные факторы, скрытые за нотацией большого O, могут заставить вас предпочесть алгоритм O (n ^ 2). Например, быстрая сортировка O(n log n) быстрее, чем сортировка вставками O(n^2), но некоторые реализации быстрой сортировки переключаются на сортировку вставками, когда разделы становятся маленькими (менее десяти элементов).

person user448810    schedule 05.02.2016
comment
Совершенно верно, люди склонны забывать вступительное предложение всех утверждений «Большое О»: существует n0, так что для всех n > n0... Кроме того, это n0 может быть на удивление большим. - person Ulrich Eckhardt; 05.02.2016
comment
Да, похожий вопрос недавно; stackoverflow.com/questions/35218322/ - person Aravind; 05.02.2016
comment
Быстрая сортировка - это O (n ^ 2) в худшем случае (хотя довольно просто избежать входных данных в худшем случае); но, чтобы использовать другой пример, быстрая сортировка часто работает лучше, чем на самом деле алгоритмы O (n lg n), такие как пирамидальная сортировка и сортировка слиянием. - person chepner; 05.02.2016

arrow_upward
1
arrow_downward

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

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

person Craig Gidney    schedule 05.02.2016

arrow_upward
-1
arrow_downward

Одна возможность - алгоритм O (n logn) является рекурсивным, но вы можете программировать O (n ^ 2) итеративно, а ваш язык программирования, который вы должны использовать, не поддерживает рекурсию.

«Предпочтительный» здесь относителен, кстати. Если набор данных был достаточно большим, вы МОГЛИ эмулировать рекурсию, используя свою собственную переменную стека, которой вы манипулируете в версии «рекурсивного» алгоритма, которая была реализована итеративно (мы должны были сделать это упражнение в классе сравнительного программирования Гая Стила в CMU). в старые времена).

person franji1    schedule 05.02.2016
comment
Если я не ошибаюсь, все рекурсивные алгоритмы можно переписать как итерационные, просто они не всегда такие простые и красивые. - person Kevin; 05.02.2016