complexity-theory - Big O Notation，我们什么时候可以合法地删除常量？

Question

我知道在 Big O Notation 中我们只考虑最高阶的前导多项式项，因为我们基本上将这个理论上的最坏情况限制在计算时间复杂度上，但有时我对何时可以合法地删除/考虑项作为常量感到困惑.例如，如果我们的等式运行在

O((n^3)/3) --> 我们取出“1/3”分数，将其视为常数，将其丢弃，然后说我们的算法运行时间为 O(n^3)。

在 O((n^3)/((log(n))^2)) 的情况下呢？在这种情况下，我们是否可以提取 1/((log(n)^2)) 项，将其视为常数，将其删除，然后最终得出结论我们的算法是 O(n^3)。看起来我们做不到，但是这个案例和上面的案例有什么区别呢？两者都可以被视为常数，因为它们的值与分子中的前导多项式项相比相对较小，但在第二种情况下，随着 n 值越来越大，分母项确实降低了最坏情况下的界​​限(收敛)。

Answer 1

在这一点上，回头看看大 O 表示法的正式定义开始是个好主意。本质上，当我们说 f(x) is O(g(x))我们的意思是存在一个常数因子 a和一个起始输入 n0这样对于所有x >= n0然后 f(x) <= a*g(x) .

举个具体例子，证明3*x^2 + 17是O(n^2)我们可以使用 a = 20和 n0 = 1 .

从这个定义中可以很容易地看出为什么常数因子会下降——这只是调整 a 的问题。补偿。至于你的1/log(n)问题，如果我们有 f(x) is O(g(x))和 g(x) is O(h(x))然后我们还有f(x) is O(h(x)) .所以是的，10*n^3/log(n) + x is O(n^3)但这不是一个更严格的上限，而且它比说 10*n^3/log(n) + x is O(n^3/log(n)) 更弱。 .对于狭窄的界限，你会想要使用 big-Theta notation相反。