为什么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)由于一个变量 k从根本上独立于其他输入集n。您通常会在排序算法分析中的比较与移动中看到这一点。

为了回答你关于为什么我们放弃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，定义成立。