分析时间复杂度（多项式与多项式）

Question

假设算法运行在

[5n^3 + 8n^2(lg(n))^4]

哪个是一阶项？它会是带有多项式还是多项式的吗？

Answer 1

对于每两个常数a>0,b>0，log(n)^a是o(n^b)(注意这里的小 o 符号)。

证明这一说法的一种方法是检查当我们在两侧应用单调递增函数（对数函数）时会发生什么。

log(log(n)^a)) = a* log(log(n))
log(n^b) = b * log(n)

因为我们知道在渐近符号中我们可以忽略常量，所以我们可以看到“哪个更大”log(n)^a或的答案n^b与“哪个更大”相同：log(log(n))和log(n)。这个答案回答起来更加直观。