给我以下时间上的复杂性,并应该将它们分配给正确的“分类”(大O表示法)。
首先:
f(n) = 1000 + log_2(n^(9n))+3*n*log_1000(n^n) -> f in O(n^2*log(n))
第二:
f(n) = 2*n^3+5 * 3^n -> f in O(3^n)
最后但并非最不重要:
f(n) = 2*n^7+5*e^n -> f in O(e^n)
现在,我要进行验证,因为我不确定自己是否正确。
f(n) = 1000 + log_2(n^(9n))+3nlog_1000(n^n)
摆脱常量和日志基础
=> O(log(n^(n)) + nlog(n^n))
从日志规则
log(a^b) = b*log(a)
=> O(nlog(n) + n*nlog(n))
=> O((n^2)*log(n))
f(n) = 2*n^3+5 * 3^n
摆脱常数
=> O(n^3 + 3^n)
指数取胜
=> O(3^n)
f(n) = 2n^7+5e^n
摆脱常数
=> O(n^7 + e^n)
再次,指数取胜
=> O(e^n)
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句