algorithm - O(1) 和 O(2) 在算法分析中有什么区别？

Question

根据大O的定义f(n) <= C*g(n) (这意味着 f(n) = O(g(n) )，可以推断出:

f(n) <= C
f(n) <= 2C

我认为这两者之间没有太大的区别。我能想到的是:

f(n) = 1 - 1 / n
f(n) = 2 - 1 / n
C = 1

但这两种复杂性有什么不同，因为它们都是恒定的复杂性？

您能否展示一些真实世界的代码来证明 O(1) 和 O(2) 之间的差异。

Answer 1

O(1)之间没有区别和 O(2) .分类为 O(1) 的算法是 O(2)反之亦然。事实上，O(c1)是O(c2)对于任何正常数 c1和 c2 .

O(c)其中 c是一个正常数仅仅意味着运行时是有界的，独立于输入或问题的大小。由此很明显(非正式地)O(1)和 O(2)是平等的。

正式地，考虑一个函数f在O(1) .然后有一个常量c这样 f(n) <= c * 1对于所有 n .让d = c / 2 .然后 f(n) <= c = (c / 2) * 2 = d * 2这表明 f是O(2) .同样，如果 g是O(2)有一个常数 c这样 g(n) <= c * 2对于所有 n .让d = 2 * c .然后 g(n) <= c * 2 = d = d * 1这表明 g是O(1) .因此O(1) = O(2) .