根据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)之间的区别。
最佳答案
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)。
关于algorithm - O(1)和O(2)在算法分析中有什么区别？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1997262/