根据大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) 之间的差异。
4842 次
8 回答
18
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对于 all n。让d = 2 * c. 那么g(n) <= c * 2 = d = d * 1这表明g是O(1)。因此O(1) = O(2)。
于 2010-01-04T02:47:22.237 回答
10
O(1) 和 O(2) 是相同的，任何 O（常数值）也是如此。
关键是既不依赖于N的某些功能。
于 2010-01-04T02:46:55.933 回答
3
没有区别。
在下图中，红线代表 O(n)，绿色曲线代表 O(n 2 )。
从红线可以看出，随着增加，2和1变得微不足道x（绿色曲线以更快的速度增长）。这就是 Big-O 表示法试图捕捉的内容；常数相对没有意义。
于 2010-01-04T02:56:31.327 回答
2
也许他们的意思是，无论输入大小（通常表示为 N）如何，这两种算法都在恒定时间内执行，但其中一种算法的速度是其两倍。但这是对大 O 表示法的滥用。
于 2010-01-04T02:50:53.943 回答
1
O(1) 和 O(2) 之间没有区别。
符号的顺序是唯一的，直到一个常数。O(f( x )) 意味着存在某个常数k，使得时间小于k f( x )。
如果某事是 O(2)，那么程序需要的一些常数k小于 2 k。因此，还有另一个常数k ' = 2 k适用于 O(1)。
于 2010-01-04T02:48:57.660 回答
0
O(1) 和 O(2) 之间没有区别。事实上，您不会使用这种表示法。它更像是 O(N) 或 O(n^2)、O(log(N)) 等。这只是算法数量级的指示。换句话说，O(1) 在时间上是恒定的。O(N) 在项目数 (N) 上是线性的，O(n^2) 在时间上是指数的，等等。
于 2010-01-04T02:50:02.070 回答
0
Big-O 表示法通常用于算法复杂度的渐近分析，即分析算法如何随着n 向无穷大增加而执行。在这种情况下，函数 f(n) 的 n 中的最高阶项将是函数的主要部分。
因此，当用 big-O 表示时，n 中的低阶项通常会从函数中删除（例如，f(n)=2n^2+4 将导致 O(n^2) 渐近 big-O 复杂度）。
在最高项为常数且不依赖于 n 的情况下，所有这些常数实际上是渐近相同的，并且通常简单地简化为 O(1)。
因此，O(2) 将被视为等同于 O(1)。
于 2010-01-04T02:51:59.557 回答
-1
您通常不写 O(2) 或 O(2n)，而是写 O(1) 和 O(n)。当然，区别在于实际速度——例如 5 秒和 10 秒。我发现你的问题有点令人困惑。
于 2010-01-04T02:47:26.633 回答