Почему O (n) лучше, чем O (nlog (n))?

Question

Я только что натолкнулся на это странное открытие: в обычной математике n * logn будет меньше, чем n, потому что log n всегда меньше 1. Так почему O (nlog (n)) больше, чем O (n)?(т.е. почему считается, что nlogn занимает больше времени, чем n)

Следует ли Big-O другой системе?

Answer 1

Это не правда. log _b n > 1 для n > b . Например, log ₂ 32 = 5.

Answer 2

Независимо от того, как две функции ведут себя при небольшом значении n, они сравниваются друг с другом, когда n достаточно велико.Теоретически, существует N такое, что для каждого данного n > N, тогда nlogn >= n.Если вы выбираете N=10, nlogn всегда больше, чем n.

Answer 3

Оказалось, я неправильно понял Logn меньше 1. Как я спросил немногих из моих старших, я узнал об этом сам сегодня, что если значение n велико, (что обычно бывает, когда мы рассматриваемБольшой O, т.е. наихудший случай), logn может быть больше 1.

Так что да, O (1)

(Я думал, что это глупый вопрос, и собирался удалить его, но потом понял, что нет вопроса, это глупый вопрос, и могут быть другие, кто получит эту путаницу, поэтому я оставил его здесь.)

Answer 4

Log (n) может быть больше 1, если n больше b. Но это не отвечает на ваш вопрос, почему O (n * logn) больше, чем O (n).

Обычно основание меньше 4. Поэтому для более высоких значений n n * log (n) становится больше, чем n. И именно поэтому O (nlogn)> O (n).

Answer 5

Этот график может помочь. log (n) возрастает быстрее, чем n и больше 1 для n, превышающего основание логарифма. https://stackoverflow.com/a/7830804/11617347