Big O вычисляет верхний предел времени выполнения относительно размера набора данных (n).
O(n*log(n)) не всегда быстрее алгоритма O(n^2), но при рассмотрении наихудшего случая , вероятно, . Алгоритм O(n^2) занимает ~ 4 раза больше времени при дублировании рабочего набора (наихудший случай), для алгоритма O(n*log(n)) он меньше. Чем больше ваш набор данных, тем больше он обычно работает быстрее, используя O(n*log(n)) -алгоритм.
РЕДАКТИРОВАТЬ : Благодаря «вреду» я исправлю неправильное утверждение в своем первом ответе: я сказал, что при рассмотрении наихудшего случая O(n^2) всегда будет медленнее, чем O(n*log(n)), это неверно, поскольку оба за исключением постоянного множителя !
Пример. Скажем, у нас наихудший случай, и у нашего набора данных размер 100.
O(n^2) -> 100 * 100 = 10000 O(n*log(n)) -> 100 * 2 = 200 (с использованием log_10)
Проблема в том, что оба можно умножить на постоянный коэффициент, скажем, мы умножим c на последний. Результат будет:
O(n^2) -> 100 * 100 = 10000 O(n*log(n)) -> 100 * 2 * c = 200 * c (с использованием log_10)
Так что для c > 50 мы получаем O(n*log(n)) > O(n^2), for n=100.
Я должен обновить свое утверждение: для каждой проблемы при рассмотрении наихудшего случая алгоритм O(n*log(n)) будет быстрее алгоритма O(n^2) для произвольно больших наборов данных.
Причина: выбор c является произвольным, но постоянным . Если вы увеличите набор данных достаточно большим, он будет доминировать при каждом выборе константы c, а при обсуждении двух алгоритмов c s для обоих констант!