algorithm - 'c' 中的 "f(n) <= c g(n)"是什么？你是怎么找到它的？

Question

我在理解此语句中“c”的概念时遇到一些问题。我需要找到一个特定的 c 吗？从技术上讲，这种说法不能总是正确的吗？就像 c 是一百万还是什么？

 Let f(n) and g(n) be functions from positive integers to positive reals.

 We say f = O(g) if there is a constant c > 0 such that f(n) <= c * g(n).


        f1(n) = n^2               O(n^2 )
        f2(n) = 2n + 20           O(n)

    which is better?

     f2(n)        2n + 20
    -------  =  -----------  <= 22
     f1(n)           n^2

         i.e. f2 = O(f1)

  if n is 1, then 22/1 ==> 22

  if n is 2, then 24/4 ==> 6

  if n is 3, then 26/9 ==> .. gets smaller

                    2
     f1(n)         n
    -------  =  ---------  <= ______ no such constant
     f2(n)       2n + 20

         i.e. f1 is NOT O(f2)

我不明白 22 是从哪里来的。我知道它是 f2(1)/f1(1)，但我不知道您为什么需要查看该分数。 c值从何而来？

我只是在努力理解这个概念，如果能给出解释，我们将不胜感激。谢谢!

Answer 1

您为大 O 符号提供的定义不完整，我怀疑这是造成您遇到困难的原因。更好的定义来自 Ronald L. Graham、Donald E. Knuth 和 Oren Patashnik，Concrete Mathematics，第 2 版，Addison–Wesley(新泽西州上马鞍河)，1994 年，第 13 页。 444(§9.2):

The formula

f(n) = O(g(n)) for all n

在这种情况下意味着存在一个常量 C 使得

|f(n)| ≤ C|g(n)| for all n […].

关键是量化——“对于所有 n”。记住这一点以备后用。

现在，回答您的问题:

• 如果您试图证明∀n : ℤ⁺。 f(n) = O(g(n))，那么你不必找到一个特定的 C——你只需要证明它存在。当然，证明一个存在的最简单方法是提供它，因此您经常会发现自己选择(或界定)一个 C。

• 即使您为 C 选择一个大得离谱的值，该陈述也不一定总是正确的。例如，∃C : ℝ。 ∀n:ℤ⁺。 |n²| > C|n|，这意味着 n² ≠ O(n)。

• 在提供的示例中，22 是常量。作者试图证明 f₂ = O(f₁)，或者 ∃C : ℝ。 ∀n:ℤ⁺。 |f2(n)| ≤ C|f₁(n)|。他们通过重新排列后者与 |f₂(n)| 的关系来做到这一点。 ∕ |f₁(n)| ≤ C，断言 C = 22，然后证明关系成立。

如果您正在为大 O 表示法苦苦挣扎，请不要感到孤单 - 几乎每个计算机科学家都至少遇到过一次这个话题。为了稍微减轻难度，Eric Lehman、F. Thomson Leighton 和 Albert R. Meyer 在他们的书中 Mathematics for Computer Science , 未发表, 2010, p. 276 (§9.7.2)，提出了一个替代的、基于限制的定义，这对我来说更容易理解:

Given nonnegative functions f, g : ℝ → ℝ, we say that

f = O(g)

如果

lim sup[x→∞] f(x) ∕ g(x) < ∞.

这个定义与具体数学中的定义完全相同，但它省去了寻找常数的困难，取而代之的是取极限的困难，这是更熟悉的领域新的计算机科学家。