因此,我无法阅读希腊语或任何其他语言,但我认为我可以充分理解所要求的内容以帮助回答:
a. (n^4 - 35n^2logn) // initial expression
= O(n^4) // 35n^2logn is always positive, so we can
// drop this subtracted term if it helps us get
// to the O class we want
= O(n^5) // n^4 grows more slowly than n^5
this is true
b. log_3(n^8)
= 8log_3(n) // law of logs, log(x^y) = ylog(x)
= 8log_8(n)/log_8(3) // law of logs, log_a(x) = log_b(x)/log_b(a)
= (8/log_8(3))log_8(n) // rearrange expression so constants are together
= O(log_8(n)) // drop the constants
this is true
c. n^2 + n
this is false; polynomials grow faster than any power of logs
d. 100n^8 + 78n^7 + 30n^5sqrt(n) + n^2 + n
= O(n^8) // drop all but the high-order term
= O(2^n) // exponentials grow faster than polynomials if the base is greater than one
this is true
e. 2^n
this is false; exponentials grow faster than polynomials if the base is greater than one
f. f(1) = 1, f(n) = f(n-1) + n
<=>
f(n) = n(n+1)/2
= (1/2)n^2 + (1/2)n
this is false; the high-order term is n^2 which grows faster than n
如果有关于具体证明其中任何一个的疑问,请让我知道,我可以更新答案。否则,您可以以此为起点编写自己的证明。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句