算法分析中O(1)和O(2)之间有什么区别？

Question

根据big 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).

Answer 2

O(1)和O(2)是相同的,任何O(常数值)也是如此.

关键在于既不依赖于N的某些功能.