如何计算 Big Oh 符号

Question

请有人告诉我2n = O(3n)是如何计算的？

以下是其他一些示例：

2^4 = O(1)
10n = O(n)
n log2(n) = O(n log n)

Answer 1

big-O 有严格的数学定义：

如果存在值 x0 >，则 f(x) 为 O(g(x)) ;= 0 且k > 0 使得对于所有 x > x0，f(x) <= k*g(x)。

要证明有关函数大 O 分类的陈述，您必须展示如何查找 x0 和 k 值。

Answer 2

2^4 = 2^4 * 1 <= 2^4 * 1

因此，2^4 是 O(1)，且常量为 2^4。

10 * n = 10 * n <= 10 * n

因此，10 * n 是 O(n)，常数为 10。

n log2 n = n log n / log 2 <= (1 / log 2) * n log n

因此，n log2 n 是 O(n log n)，常数为 1 / log 2。

Answer 3

一般来说，使用渐近符号的定义，然后产生 f(n) = O(g(n)) 的证明，其中 f(n) 是您的函数，g(n) 是您要证明的界限。

对于您的第一个示例：

2n =? O(3n)
f(n) = 2n, g(n) = 3n
need c such that for n > n0, f(n) <= c*g(n); guess c = 1
We have f(n) = 2n <= 3n = c*g(n) for n >= 0, so
2n = f(n) = O(g(n)) = O(3n)

对于您的第二个示例：

2^4 =? O(1)?
f(n) = 2^4, g(n) = 1
need c such that for n > n0, f(n) <= c*g(n); guess c = 2^4 + 1
We have f(n) = 2^4 <= 2^4 + 1 = c*g(n), so
2^4 = f(n) = O(g(n)) = O(1)

您的第三个示例实际上等同于第一个示例。

你的第四个例子是错误的；这是假的

n log^2(n) = O(n log n)

这是真的

n log(n^2) = O(n log n)

但那是不同的表达方式。要看出 n log^2(n) 不是 O(n log n)，我们可以这样论证：设 c 是任意固定常数。我们可以找到一个 n 使得 c*n*log(n) < n*log^2(n)。我们得到

c*n*log(n) < n*log^2(n)
c < log(n)

所以选择 n = 2^(c+1)。因此，不存在这样的n0，对于n＞1， n0, f(n) <= c*g(n)。

编辑：在第四个示例中，如果您的意思是“log2(n)”n 的对数基数二，那么是的，nlog2(n) = O(nlogn)。通常，在计算复杂性算法时，除非另有说明，否则对数被理解为以 2 为底。抱歉造成混乱。

Answer 4

有多种方法可以证明这一点：

其中一种可能是使用极限：

f(n) = O(g(n)) iff：如果以下成立：

                f(n)
   limsup    ----------  < infinity
x->infinity     g(n)

因此，如果您取 2n/(3n) 在极限中，这是1.5。