Заказ списка сложностей (Big O)

Question

Приведен список сложностей:

Как вы тогда заказываете в их Big O порядке?

Я думаю, что ответ ниже?

Вопрос теперь в том, как log(n!) становится n log(n). Также я не знаю, получил ли я n! и (n-1)! право. Возможно ли, что c ^ n может быть больше, чем n !? Когда с> п?

В общем, как я могу визуализировать такую ​​проблему Big O ... это заняло у меня довольно много времени ... по сравнению с кодированием до сих пор ... Любые ресурсы, видео Ресурсы MIT Open Courseware, кое-что с объяснением

Answer 1

Возможно, вы захотите увидеть, как растут функции.Вот краткий сюжет от Wolfram Alpha:

ссылка

В общем, n^n растет намного быстрее, чем c^n для любого n больше, чем некоторые n_0 (потому что n будет обгонять c в некоторый момент, даже если c очень велико).log растет намного медленнее, чем квадратичный или экспоненциальный, и немного быстрее линейного.

Для O(log(n!)) = O(nlogn) я полагаю, что было нечто, называемое приближением Стирлинга.Это сводится к тому, что O(n!) = O(n^n) как n! = n*(n-1)*(n-2)*...*2*1, поэтому n^n = n*n*n*...*n является верхней границей.Можно доказать, что это также и нижняя граница, но вам это не нужно.

Начиная с log(n^n) = nlogn по правилам журнала, O(log(n!) = O(log(n^n)) = O(nlogn).