Являются ли алгоритмы O (n log n) всегда лучше, чем все алгоритмы O (n ^ 2)?

Question

Когда я пытаюсь правильно понять Big-O, мне интересно, правда ли, что O(n log n) алгоритмы всегда лучше, чем все O(n^2) алгоритмы.

Существуют ли какие-либо конкретные ситуации, когда O(n^2) будет лучше?

Я много раз читал, что при сортировке, например, алгоритм O(n^2), такой как пузырьковая сортировка, может быть особенно быстрым, когда данные почти отсортированы, поэтому он будет быстрее, чем алгоритм O(n log n), напримеркак сортировка слиянием, в данном случае?

Answer 1

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

См. Здесь для некоторых внутренних реализаций.

Answer 2

В дополнение к ответу @ cadaniluk:

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

Также никогда не забывайте, что нотация Big-O скрывает константы и аддитивные функции более низких порядков.Таким образом, алгоритм с наихудшей сложностью O (n log n) на самом деле может иметь сложность 2 ^ 10000 * n * log n, а ваш алгоритм O (n ^ 2) может фактически работать в 1/2 ^ 1000 n ^ 2.Таким образом, для n <2 ^ 10000 вы действительно хотите использовать «более медленный» алгоритм. </p>

Answer 3

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

В этом определении вы должны учитывать некоторые аспекты:

1. Обозначение Big-O является верхней границей сложности алгоритма, что означает, что для некоторых входных данных (например, упомянутых вами)о алгоритмах сортировки) алгоритм с наихудшей сложностью Big-O может на самом деле работать лучше (пузырьковая сортировка выполняется в O(n) для уже отсортированного массива, в то время как сортировка слиянием и быстрая сортировка всегда занимают не менее O(n log n));
2. Нотация Big-O описывает только класс сложности, скрывая все постоянные факторы, которые в реальных сценариях могут иметь значение.Например, алгоритм со сложностью 1000000 x, который находится в классе O(n), работает хуже, чем алгоритм со сложностью 0.5 x^2 (класс O(n^2)) для входных данных, меньших чем 2000000. В основном нотация Big-O говорит вам, что длядостаточно большой вход n, алгоритмы O(n) будут работать лучше, чем O(n^2), но если вы работаете с небольшими входами, вы все равно можете предпочесть последнее решение.

Answer 4

O (n log n) лучше, чем O (n ² ) асимптотически .

Big-O, Big-Theta, Big-Omega, всеони измеряют асимптотическое поведение функций, т. е. как ведут себя функции, когда их аргумент приближается к определенному пределу.

O (n log n) функции растут медленнее, чем функции O (n ² )это то, что по сути говорит Big-O.Однако это не означает, что O (n log n) всегда быстрее.Это просто означает, что в некоторой точке функция O (n log n) всегда будет дешевле при постоянно растущем значении n.

На этом изображении f (n) = O (g (n)).Обратите внимание, что существует диапазон, где f (n) на самом деле дороже, чем g (n), даже если он асимптотически ограничен g (n).Однако, когда речь идет об ограничениях или асимптотике в этом отношении, f (n) превосходит g (n) «в долгосрочной перспективе», так сказать.