分析时间复杂性(多对数与多项式)

Question

假设算法在上运行

[5n^3+8n^2（lg（n））^4]

第一个订单项是什么？它会是一个多对数的还是多项式的？

Answer 1

对于每两个常数a>0,b>0，log(n)^a都在o(n^b)中（请注意此处的小o表示法）。

证明这一说法的一种方法是研究当我们在两边应用单调递增函数时会发生什么：log函数。

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

由于我们知道在渐近符号中可以忽略常数，我们可以看到"哪个更大"log(n)^a或n^b的答案与"哪个更"相同：log(log(n))和log(n)。这个答案要直观得多。