多项式方程：算法

Question

我一直在 material 阅读有关算法的内容（在 Java 中）。

这道题问的是哪个多项式表达式是正确的

我需要进一步material了解如何对每个表达式进行分类

正确或不正确。

Answer 1

所以，我看不懂希腊语或其他任何语言，但我想我可以充分理解所要求的内容来帮助回答：

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

如果有关于具体证明其中任何一个的问题，请告诉我，我可以更新答案。否则，您可以使用这些作为起点来编写自己的证明。

多项式方程：算法

Polynomial equations : Algorithms

algorithm

complexity-theory