多项式方程:算法

C96

我一直在阅读有关算法的资料(使用Java)。

该问题询问哪个多项式表达式正确。

我需要进一步的材料来理解如何对每个表达式进行分类

正确与否。

Java中的算法:哪个多项式方程是正确的

帕特里克87

因此,我无法阅读希腊语或任何其他语言,但我认为我可以充分理解所要求的内容以帮助回答:

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] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章