algorithm - 在分析算法的时间复杂度时，为什么要舍弃度数最大项的常​​量

Question

假设我有以下内容:T(n) = 5n^2 +2n这个的渐近紧界是 theta n^2。我想了解删除 5 背后的原因。我了解为什么我们忽略低阶项。

Answer 1

引用 big-O 的定义。

为简单起见[​​]，如果存在常数 C 和 M 使得 n > M，0 <= g(n) < Cf(n)，那么我们定义函数 g 为 O(f)。

在F中存在正常乘数不会影响这一点，只需适本地选择c即可。通过选择大于 5 的 C 值和足够大的 M 值，+2n 无关紧要，您的示例 T 为 O(n^2)。例如，对于 n > 2，事实是 5n^2 + 2n < 6n^2(因为 n^2 > 2n)，因此对于 C= 6 和 M = 2，我们看到 T(n) 是 O(n ^2).

所以 T(n) 确实是 O(n^2)，也是 O(5n^2) 和 O(5n^2 + 2n)。这些事实中最有趣 是它的复杂度为 O(n^2)，因为它是最简单的表达式，而其他两个在逻辑上是等价的。如果我们要比较不同函数的复杂度，那么我们要使用简单的表达式。

对于 big-Theta，请注意，当 f 和 g 反过来时，我们可以玩同样的把戏。 “g是Theta(f)”这个关系是一个等价关系，那么我们要选择什么作为T的等价类的代表成员呢？最简单的。

[*] 为了让事情不那么简单，我们通过使用 limsup 而不是简单的限制来处理负数。我上面的定义其实已经足够了，但不是必须的。