algorithm - 为什么大 O 表示法中的加法常数无关紧要？

Question

在大 O 符号的定义中，我们只关心 C 系数:

f(n) ≤ Cg(n) for all n ≥ k

为什么我们不关心A:

f(n) ≤ Cg(n) + A for all n ≥ k

Answer 1

这里确实有两种情况需要考虑。对于初学者，假设您的函数 g(n) 具有以下属性:对于 n 的所有“足够大”选择，g(n) ≥ 1。那样的话，如果你知道的话

f(n) ≥ cg(n) + A,

那你也知道

f(n) ≥ cg(n) + Ag(n),

所以

f(n) ≥ (c + A)g(n).

换句话说，如果你的函数 g 总是至少为 1，那么用 cg(n) + A 的形式来限制 f(n) 等价于用 c'g(n) 的形式来限制它对于一些新的常量 c'。从这个意义上说，在大 O 表示法的定义中增加一些额外的灵 active ，至少在这种情况下，不会有什么不同。

在算法分析的上下文中，几乎每个你可能绑定(bind)的函数 g(n) 都至少是一个，所以我们可以通过选择 g 的更大倍数来“吞噬”那个额外的附加项.

但是，在许多情况下，big-O 表示法也用于绑定(bind)随着 n 增加而减少的函数。例如，我们可以说某些算法给出正确答案的概率是 O(1/n)，其中函数 1/n 作为 n 的函数下降到 0。在这种情况下，我们使用大 O 表示法来讨论函数下降的速度有多快。例如，如果成功概率为 O(1/n²)，则假设 n 足够大，这比早期的 O(1/n) 成功概率更好。在那种情况下，在大 O 表示法的定义中允许附加项实际上会破坏事情。例如，直觉上，函数 1/n² 下降到 0 的速度比函数 1/n 快，使用大 O 表示法的正式定义你可以看到这一点，因为 1/n ² ≤ 1/n 对于所有 n ≥ 1。但是，根据您对大 O 符号的修改定义，我们也可以说 1/n = O(1/n²) , 因为

1 / n ≤ 1 / n² + 1 for all n ≥ 1,

这只是因为加法 1 项限制了 1/n 项，而不是我们最初可能感兴趣的 1/n²。

所以对你的问题的长答案是“你上面提出的定义等同于 big-O 的常规定义，如果我们只限于 g(n) 作为函数不降为零的情况n，并且在 g(n) 确实将零作为 n 的函数的情况下，您的新定义并不是特别有用。”