1
Рассмотрим пример, , если п = 4Почему n log (n) имеет более высокое доминирование, чем n?
н лог (п) = 4 * журнал (4) = 2,408
п = 4
Тогда как н лог (п)> п ???
A
ответ
2
Знаки Big O предполагают, что n велико. n = 4 не имеет отношения к анализу сложности.
В общем случае, если вы посмотрите на соотношение между обоими: n.log(n)/n = log(n) при условии, что n> 0.
При п становится большим, это отношение стремится к бесконечности, а это означает, что n.log(n) принимает «бесконечно» больше времени, чем n, и, таким образом n.log(n) доминирует n.
+0
Мне было бы очень интересно узнать, как я заработал голос. :) –
+0
[tag: Big-O] ничего не предполагает. – xenteros
+2
Ну, это не то, чему меня учили в математическом классе. :) Big O и обозначения Ландау в целом асимптотики, поэтому имеет значение, когда n стремится к бесконечности: https://en.wikipedia.org/wiki/Big_O_notation –
1
big-o описывает, как быстро функции растут асимптотически. nlogn растет быстрее, чем n, поэтому в ваших обозначениях O(nlogn) > O(n), однако это не правильная нотация.
Фактически O(nlogn) - это набор, а также O(n) есть. Существует также связь между ними:
Просто для уточнения необходимости согласно комментариям: все логарифмы растут так же быстро, в соответствии с big-o:
Смежные вопросы
- 1. (log (n))^log (n) и n/log (n), что быстрее?
- 2. Каков порядок (log n)/(log (log n))?
- 3. Почему этот цикл возвращает значение O (n log log n), а не O (n log n)?
- 4. Сложность алгоритма, log^k n vs n log n
- 5. Почему сортировка строки O (n log n)?
- 6. Как O (n log n) отличается от O (log n)?
- 7. Является ли log (n!) = Θ (n · log (n))?
- 8. n^2 log n сложность
- 9. Является ли O (n) + O (n log n) равным O (n log n)?
- 10. O (N log N) Сложность - аналогично линейному?
- 11. Самый близкий парный алгоритм из (n log^2 n) в (n log n) time
- 12. Каким будет журнал (O (n * log (n)))?
- 13. Big Oh for (n log n)
- 14. Почему n ++ выполняется быстрее, чем n = n + 1?
- 15. n log n и скорость компьютера
- 16. Является ли O (log n) всегда быстрее, чем O (n)
- 17. - это что-то меньшее, чем n - log n?
- 18. Почему худший случай слияния по-прежнему остается n log n?
- 19. Если f (n) = O (g (n)), то log (f (n)) = O (log (g (n))?
- 20. Является большим o для следующего O (n^2 * log (n)) или O (n^3 * log (n))
- 21. Вычисление ноты Not-O, O (n) * O (log n) = O (n log n)
- 22. Когда c> 0 Log (n) = O (n)? Не знаю, почему это не O (log n)
- 23. Является ли log (n^c) равным O (log (n))
- 24. стабильная сортировка в O (n log (log n))
- 25. T (n) = T (n-1) + O (log n) $ является T (n) = O (n^2) или T (n) = O (n log n)
- 26. O (n log n) Алгоритм сложности времени?
- 27. O (n^log n) алгоритм обнаружения столкновений
- 28. Big O N^2 (Log N)
- 29. Как вычислить n log n = c
- 30. Отношение повторения: T (n/16) + n log n
Потому что это все о асимптотике. Посмотрите на определение для Landau-нотации (и попробуйте заполнить ваш пример)! – sascha
Теперь попробуйте с n 4 000 000 000 – RemcoGerlich
Обратите внимание, что 'log' зависит от базы. Вы используете базу 10, т. Е. «Log (4, 10)» и «log (n, b) <1', если' n' меньше базовой 'b', но, очевидно, это не является нормой. –