algorithm - 恒定时间复杂度的大 O

Question

如果我有像 c1+c2+c3 这样的恒定时间复杂度，那么我知道这将需要线性时间。我想用大 O 表示法来表达它。如果时间复杂度是 f(n)= 2n+3 那么我们写 O(n) 然后证明 f(n) < cg(n)，但是对于恒定的时间我们怎么做呢？

标签： algorithmdata-structures

Answer 1

如果你知道算法的时间复杂度是一些常数的组合，比如 c1 + c2 + c3，那么你可以定义一个函数 f(x) = c1 + c2 + c3 = c。然后，使用大O的定义，即

f(x) = O(g(x)) 当 x 趋于无穷时

当且仅当存在一个正实数 M 和一个实数 x0 使得

|f(x)| <= Mg(x) 对于所有 x >= x0

我们可以说 f(x) = c 是 O(1) 且 g(x) = 1。原因是我们可以通过选择 M 为常数 c 来满足上述定义的要求，而 x0 在这里无关紧要因为时间复杂度不取决于 x 的值。