algorithm - 为什么 Big-O 表示法使用 O(1) 而不是 O(k)？

Question

如果我正确理解 Big-O 表示法，k那么算法效率应该是一个常数时间。考虑到它需要可变时间，为什么要考虑恒定时间O(1)而不是？O(k)线性增长( O(n + k) )使用此变量将时间向右移动特定的时间量，那么对于恒定复杂性为什么不一样呢？

Answer 1

不存在这样的线性增长渐近O(n + k)，其中k是一个常数。如果k是一个常数并且你回到算法增长率的极限表示，你会看到O(n + k) = O(n)因为常数在极限中下降。

您的答案可能是O(n + k)由于一个从根本上独立于其他输入集的变量 。您通常会在排序算法分析中的比较与移动中看到这一点。kn

为了回答你关于为什么我们放弃kBig-O 表示法的问题（我认为它的教学很差，导致所有这些混乱），O() 的一个定义（我记得）如下：

Read: f(n) is in O( g(n) ) iff there exists d and n_0 where for all n > n_0,
                                         f(n) <= d * g(n)

让我们尝试将其应用于我们的问题，其中 k 是一个常数，因此 f(x) = k 和 g(x) = 1。

• 是否存在满足这些要求的d和？n_0

琐碎，答案当然是肯定的。选择 d >k并且对于 n > 0，定义成立。