complexity-theory - 算法复杂度：log(x^2 + x^3) = O(?)

Question

虽然我了解编程中算法复杂度和对数复杂度的概念，但我不知道如何确定包含不同幂变量的对数复杂度。

这里有些例子：

log(x^2 + 3x^3) = O(?)

log(x^3 + 5) = O(?)

任何帮助将不胜感激。

谢谢你。

Answer 1

O(log(x))

只是因为数学规则（严格来自对数的定义）log(xk) = k⋅log(x)

此外，我们知道 O 是渐近乘法符号，因此乘以常数不会影响它。

证明：

log(x² + 3x³) ≤ log(4x³) ≤ log(x⁴) 对于足够大的 x

所以log(x²+3x³) ≤ log(4x³) ≤ log(x⁴) = 4⋅log(x)我们知道根据定义是 O(log(x))

这是上 O 界的证明

在另一个方向（显示不需要但您可能感兴趣的 Theta）

log(x²+3x³) ≥ log(x²) >= 2⋅log(x)根据定义，这是 O(log(x))