如果你看到这则信息,这表示下载可汗学院的外部资源时遇到困难.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

主要内容

大θ (大Theta) 符号

让我们看一下线性搜索的简单实现:
var doLinearSearch = function(array, targetValue) {
  for (var guess = 0; guess < array.length; guess++) {
    if (array[guess] === targetValue) { 
        return guess;  //找到啦!
    }
  }
  return -1;  //没找到
};
让我们用n表示数组的大小 (array.length)。for 循环可以运行的最大次数为n,当数组中不存在要搜索的值时, 就会出现这种最坏的情况。
每次for循环迭代时,它必须做几件事:
  • guessarray.length进行比较
  • array[guess]targetValue进行比较
  • 返回guess的值
  • guess自增。
这些小计算中的每一个在每次执行时都会花费常量时间。如果for循环迭代 n 次,则对于所有n次循环来说运行时间是c1nc1是所有单次循环中所需计算时间的和。我们无法说c1 究竟是多少,因为他取决于计算机的计算速度,编译器或解释器将程序解释成可执行代码的时间,或者其他的一些因素。
代码有一点额外开销用来进行for循环(包括将guess初始化为0) ,结果可能返回-1。 让我们来将这个额外开销的时间记为 c2, 他是个常量。因此,线性搜索最坏情况的总运行时间是c1n+c2
正如我们讨论的, 系数常量c1 和低阶项c2无法告诉我们运行时间的增长速率。重要的是,线性搜索的最坏情况运行时间会随着数组大小n的增长而增长。我们使用符号 Θ(n)来标识这个运行时间。 它是希腊字母 "theta", 我们将之记作"big-Theta of n" 或者仅仅是 "Theta of n."
当我们说一个特定的运行时间是 Θ(n)时, 我们说,一旦n变得足够大, 存在某些常量k1k2,运行时间至少是k1n,至多是k2n。下面是如何思考 Θ(n):
n很小时, 我们不在乎运行时间 k1n 比起 k2n 谁更快。但是,一旦n变得足够大——在虚线上或右侧——运行时间必须处于 k1nk2n 之间。只要这些常量 k1k2 存在, 我们就说运行时间是 Θ(n)
我们并不限制 big-Θ符号中的 n。我们可以使用任何函数, 如 n2nlog2n,或者关于n的任何其他函数。下面是如何思考一些函数 f(n)的运行时间Θ(f(n)):
一旦 n 足够大, 运行时间处于 k1f(n)k2f(n)之间。
实际上, 我们只是去掉了常量和低阶项。使用 big-Θ 标记的另一个优点是, 我们不必担心使用的是哪些时间单位。例如,假设计算的运行时间为6n2+100n+300秒。或者也可能是毫秒。当使用big-Θ 标记时,你不用管它。你也可以去掉系数和低阶项100n+300,你只需要说,运行时间是 Θ(n2)
当我们使用big-Θ符号时, 我们说的是我们在运行时间上有一个 渐近紧约束 。"渐近"是因为它只对n起作用。"紧约束",因为我们已经将运行时间约束在常量系数的上限和下限中。
本内容是 达特茅斯计算机科学 教授 Thomas CormenDevin Balkcom,与可汗学院的计算课程团队合作完成。内容获得许可 CC-BY-NC-SA

想加入讨论吗?

尚无帖子。
你会英语吗?单击此处查看更多可汗学院英文版的讨论.