Что лучше: O (n log n) или O (n ^ 2)

Хорошо, поэтому у меня есть этот проект, который я должен сделать, но я просто этого не понимаю. Дело в том, что у меня есть 2 алгоритма. O (n ^ 2) и O (n * log ₂ n).

В любом случае, я узнаю в информации о проекте, что если n < 100, то O (n ^ 2) более эффективен, но если n >= 100, то O (n * log ₂ n) более эффективен. Я должен продемонстрировать пример, используя цифры и слова или нарисовать фотографию. Но дело в том, что я не понимаю этого, и я не знаю, как это продемонстрировать.

Кто-нибудь может помочь мне понять, как это работает?

Приветствуем заранее!

EDIT: Спасибо всем за ответы.

Ответ 1

Просто спросите wolframalpha, если у вас есть сомнения.

В этом случае говорится:

     n log(n)
lim --------- = 0
       n^2

Или вы также можете сами рассчитать лимит:

     n log(n)        log(n)   (Hôpital)       1/n          1
lim --------- = lim --------      =     lim ------- = lim --- = 0
       n^2             n                       1           n

Это означает, что n^2 растет быстрее, поэтому n log(n) меньше (лучше), когда n достаточно высок.

Ответ 2

Хороший вопрос. На самом деле, я всегда показываю эти 3 фотографии:

n = [0; 10]

n = [0; 100]

n = [0; 1000]

Итак, O(N*log(N)) намного лучше, чем O(N^2). Он намного ближе к O(N), чем к O(N^2).

Но ваш алгоритм O(N^2) работает быстрее N < 100 в реальной жизни. Есть много причин, почему это может быть быстрее. Возможно, из-за лучшего выделения памяти или других "неагрессивных" эффектов. Может быть, алгоритм O(N*log(N)) требует некоторой фазы подготовки данных или O(N^2) итераций короче. Во всяком случае, запись Big-O подходит только в случае достаточно больших Ns.

Если вы хотите продемонстрировать, почему один алгоритм работает быстрее для небольших Ns, вы можете измерить время выполнения 1 итерации и постоянные накладные расходы для обоих алгоритмов, а затем использовать их для коррекции теоретического графика:

Пример

Или просто измерить время выполнения обоих алгоритмов для разных Ns и построить эмпирические данные.

Ответ 3

Обозначение Big-O является обозначением асимптотической сложности. Это означает, что он вычисляет сложность, когда N сколь угодно велико.

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

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

Кстати, не записывайте основы журнала. Нотация Big-O игнорирует константы - O (17 * N) совпадает с O (N). Так как log ₂ N просто ln N / ln 2, базис логарифма является просто другой константой и игнорируется.

Ответ 4

Давайте сравним их,

С одной стороны, мы имеем:

n^2 = n * n

С другой стороны, мы имеем:

nlogn = n * log(n)

Поместив их сбоку:

n * n    versus    n * log(n)

Разделим на n, который является общим термином, чтобы получить:

n    versus    log(n)

Давайте сравним значения:

n = 10           log(n) ~ 2.3
n = 100          log(n) ~ 4.6
n = 1,000        log(n) ~ 6.9
n = 10,000       log(n) ~ 9.21
n = 100,000      log(n) ~ 11.5
n = 1,000,000    log(n) ~ 13.8

Итак, мы имеем:

n >> log(n) for n > 1

n^2 >> n log(n) for n > 1

Ответ 5

Во-первых, не совсем корректно сравнивать асимптотическую сложность, смешанную с N-ограничением. Я., могу утверждать:

O(n^2) медленнее, чем O(n * log(n)), потому что определение нотации Big O будет включать n is growing infinitely.
Для конкретного N можно сказать, какой алгоритм быстрее, просто сравнивая N^2 * ALGORITHM_CONSTANT и N * log(N) * ALGORITHM_CONSTANT, где ALGORITHM_CONSTANT зависит от алгоритма. Например, если мы дважды пройдем массив, чтобы выполнить нашу работу, асимптотическая сложность будет O(N), а ALGORITHM_CONSTANT будет 2.

Также я хотел бы упомянуть, что O(N * log2N), который я предполагаю, логарифм на основе 2 (log ₂ N) на самом деле тот же, что и O(n * log(n)) из-за свойств логарифма.

Ответ 6

У нас есть два способа сравнить два Algo - > первый способ - очень просто сравнить и применить предел

T1(n)-Algo1

T2(n)=Alog2

  lim  (n->infinite) T1(n)/T2(n)=m

(i), если m = 0 Algo1 быстрее, чем Algo2

(ii) m = k Оба одинаковы

(iii) m = бесконечный Algo2 быстрее

* Второй путь довольно прост, так как сравним с 1-м там, вы просто берете журнал обоих, но не игнорируете multi constant

             Algo 1=log n

             Algo 2=sqr(n)

             keep log n =x

             Any poly>its log


   O(sqr(n))>o(logn)