#big-o
#big-o
Вопрос:
Учитывая список сложностей:
Как вы упорядочиваете их в порядке Big O?
Я думаю, ответ ниже?
Теперь вопрос в том, как это сделать log(n!) n log(n) . Также я не знаю, получил ли я n! и (n-1)! правильно. Возможно ли, что c ^ n может быть больше n !? Когда c> n?
В общем, как мне визуализировать такую большую проблему… мне потребовалось довольно много времени, чтобы сделать это … по сравнению с кодированием до сих пор… Любые ресурсы, видео, открытые учебные ресурсы MIT, что-нибудь с объяснением
Комментарии:
1. Я нашел очень поучительным построение различных функций в Excel, чтобы визуально понять, как каждая из них растет с увеличением N.
Ответ №1:
Возможно, вы захотите посмотреть, как растут функции. Вот краткий график из Wolfram Alpha:
В общем, n^n растет намного быстрее, чем c^n для любого n большего, чем некоторые n_0 (потому n c что в какой-то момент обгонит, даже если c чрезвычайно велико). логарифм растет намного медленнее, чем квадратичный или экспоненциальный, и немного быстрее, чем линейный.
O(log(n!)) = O(nlogn) Я полагаю, что было нечто, называемое приближением Стирлинга. Это сводится к тому, что O(n!) = O(n^n) as n! = n*(n-1)*(n-2)*...*2*1 , so n^n = n*n*n*...*n — это верхняя граница. Можно доказать, что это также нижняя граница, но вам это не нужно.
Поскольку log(n^n) = nlogn по правилам журнала, O(log(n!) = O(log(n^n)) = O(nlogn) .