Я рассматривает функциюBig O of f (n) = N! + 2^N
f(n) = N! + 2^N
Предположительно, это
O(N^N)
Я не совсем уверен, почему это, или как доказать, что это правда.
Я думаю, что это
O(N!)
Можете ли вы дать объяснение, почему Big O для
f(n) = N! + 2^N => O(N^N)
Это действительно O(N!) и так N! является O(N^N) (потому что N! < = N^N для всех N> 0), все в O(N!) также находится в O(N^N).
это '=>' not '<=' – user2485710
Рассматривается ли это относительно жесткая граница? Есть особые отношения между N! и N^N Я должен рассмотреть во всех моих проблемах с Big O? – ceptno
@ user2485710 Нет, это <=. N^N является «N * N * ... * N'. 'N!' - '1 * 2 * ... * N'. В обоих случаях у вас одинаковое количество терминов, а термины в 'N!' Все меньше или равно N, в то время как члены в 'N^N' - все точно' N'. Поэтому 'N! <= N^N'. Также обратите внимание, что если N! были больше, чем 'N^N' (по непостоянному фактору),' N! 'не будет' O (N^N) ', поэтому предпосылка вопроса будет ложной. – sepp2k
Этот вопрос не соответствует теме, потому что речь идет не о программировании. Это действительно на [cs.se] –
, потому что N! BIG, действительно BIG http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions, для получения дополнительной информации у нас есть угол CS, как указано выше – user2485710
Моя ошибка @MikeW. В будущем я поставил бы свои вопросы о Big O. – ceptno