Big O Notation: различия между O (n ^ 2) и O (n.log(n))?

Ответ 1

n ^ 2 усложняется быстрее.

Ответ 2

Big O вычисляет верхний предел времени выполнения относительно размера набора данных (n).

An O(n*log(n)) не всегда быстрее, чем a O(n^2), но при рассмотрении наихудшего случая это, вероятно, есть. Алгоритм O(n^2) принимает ~ 4 раза дольше, когда вы дублируете рабочий набор (худший случай), для O(n*log(n)) -algorithm it less. Чем больше ваш набор данных, тем чаще он становится быстрее с помощью алгоритма 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 произволен, но константа. Если вы увеличите набор данных достаточно большим, он будет доминировать над каждым выбором константы2 > c, а при обсуждении двух алгоритмов c для обоих постоянных!

Ответ 3

Вам нужно быть более конкретным о том, что вы просите, но в этом случае O(n log(n)) быстрее

Ответ 4

n log(n) растет значительно медленнее

Ответ 5

Алгоритмы, выполняющиеся в O (nlog (n)) времени, обычно быстрее, чем те, которые работают в O (n ^ 2).

Big-O определяет верхнюю границу производительности. Поскольку размер набора данных растет (n), требуется время, затрачиваемое на выполнение задачи. Вы можете быть заинтересованы в курсе iTunes U из MIT.

Ответ 6

Обозначение "Big Oh" дает оценку верхней границы роста времени работы алгоритма. Если алгоритм должен быть O (n ^ 2) наивным образом, он говорит, что при n = 1 он принимает max. 1 единица, при n = 2 - макс. время 4 единицы и так далее. Аналогично для O (n log (n)), он говорит, что выращенный будет таким, чтобы он подчинялся верхней границе O (n log (n)). (Если я более чем наивный, пожалуйста, исправьте меня в комментарии).

Я надеюсь, что это поможет.