7.1.1. 下界¶

大 O 记法 描述的是上界。 换句话说，大 O 记法陈述的是：对规模为 \(n\) 的某一类输入 （通常是最坏的这类输入、所有可能输入的平均，或最好的这类输入）， 算法对某种资源（通常是时间）所需的最大量。

类似的记法也用于描述算法对某一类输入所需资源的最小量。 与大 O 记法一样，它度量的是算法的增长率。 与大 O 记法一样，它对任何资源都适用， 但我们最常度量的是所需时间的最小量。 同样，与大 O 记法一样，我们度量的是某一特定类别输入所需的资源： 规模为 \(n\) 的最坏情况、平均情况或最好情况输入。

算法（或后文将说明的问题）的 下界 用符号 \(\Omega\) 表示，读作 "big-Omega" 或简称 "Omega"。 下面 \(\Omega\) 的定义与大 O 的定义相对称。

若 \(\mathbf{T}(n)\) 是非负值函数，则当存在两个正常数 \(c\) 和 \(n_0\) ，使得对所有 \(n > n_0\) 都有 \(\mathbf{T}(n) \geq c g(n)\) 时，\(\mathbf{T}(n)\) 属于集合 \(\Omega(g(n))\) 。 [1]

上面例子中的方程也属于 \(\Omega(n)\) 。 然而，与大 O 记法一样，我们希望得到尽可能"紧" （对 \(\Omega\) 记法而言是尽可能大）的界。 因此，我们更愿意说这个运行时间属于 \(\Omega(n^2)\) 。

回想在整数数组中查找值 \(K\) 的顺序查找算法。 在平均情况和最坏情况下，这个算法属于 \(\Omega(n)\) ， 因为在平均情况和最坏情况下，我们都必须检查 至少 \(cn\) 个值 （其中 \(c\) 在平均情况下为 1/2，在最坏情况下为 1）。

7.1.2. Theta 记法¶

大 O 和 \(\Omega\) 的定义为我们提供了描述算法上界的方法 （如果我们能为规模为 \(n\) 的某一类输入找到最大代价的方程）， 以及描述算法下界的方法 （如果我们能为规模为 \(n\) 的某一类输入找到最小代价的方程）。 当上界和下界在常数因子范围内相同时， 我们用 \(\Theta\) （big-Theta）记法来表示。 如果算法属于 \(O(h(n))\) 并且 属于 \(\Omega(h(n))\) ， 就说它是 \(\Theta(h(n))\) 。 注意，对 \(\Theta\) 记法我们省略"属于"一词， 因为 \(\Theta\) 相同的两个方程之间存在严格相等关系。 换句话说，如果 \(f(n)\) 是 \(\Theta(g(n))\) ， 那么 \(g(n)\) 就是 \(\Theta(f(n))\) 。

因为顺序查找算法在平均情况下既属于 \(O(n)\) 又属于 \(\Omega(n)\) ， 所以我们说它在平均情况下是 \(\Theta(n)\) 。

给定一个描述算法时间需求的代数方程， 其上界和下界总是吻合的。 这是因为在某种意义上，我们对该算法有了完美的分析， 并由这个运行时间方程体现出来。 对许多算法（或它们作为程序的实例化）而言， 很容易得出定义其运行行为的方程。 最常用算法的分析已为人所熟知， 我们几乎总能给出它们的 \(\Theta\) 分析。 然而， NP-Complete 这一类问题都没有确定的 \(\Theta\) 分析， 只有一些不能令人满意的大 O 和 \(\Omega\) 分析。 甚至有些"简单"程序也很难分析。 目前没有人知道下面这段代码的真正上界或下界。

• Java
• C++

while (n > 1)
  if (ODD(n))
    n = 3 * n + 1;
   else
     n = n / 2;

while (n > 1)
  if (ODD(n))
    n = 3 * n + 1;
   else
     n = n / 2;

虽然一些教科书和程序员会随口说某算法是某代价函数的"阶"或"大 O"， 但一般而言，只要我们对算法有足够的了解、 确信其上界和下界确实吻合， 就最好使用 \(\Theta\) 记法而不是大 O 记法。 只要我们的知识水平允许， OpenDSA 模块都会优先使用 \(\Theta\) 记法而非大 O 记法。 分析某些算法的能力所限，可能要求我们使用大 O 或 \(\Omega\) 记法。 在少数明确讨论问题或算法的上界或下界的情形下， 会使用相应的记法而不使用 \(\Theta\) 记法。

7.1.3. 函数分类¶

给定增长率用代数方程表示的函数 \(f(n)\) 和 \(g(n)\) ， 我们可能想确定其中一个是否比另一个增长得更快。 最好的做法是求这两个函数当 \(n\) 趋于无穷大时的极限，

如果极限趋于 \(\infty\) ，那么 \(f(n)\) 属于 \(\Omega(g(n))\) ，因为 \(f(n)\) 增长得更快。 如果极限趋于零，那么 \(f(n)\) 属于 \(O(g(n))\) ， 因为 \(g(n)\) 增长得更快。 如果极限趋于某个非零常数， 那么 \(f(n) = \Theta(g(n))\) ，因为两者以相同的速率增长。

Settings

Saving...
Server Error
Resubmit

7.1.4. 小结练习¶