主要内容

课程: 计算机科学理论 > 单元 1

课程 3: 渐近符号

大θ (大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循环迭代时，它必须做几件事：

将 guess 与 array.length进行比较
将 array[guess] 与 targetValue进行比较
返回guess的值
将 guess自增。

这些小计算中的每一个在每次执行时都会花费常量时间。如果for循环迭代

n

次，则对于所有

n

次循环来说运行时间是

c_{1} \cdot n

，

c_{1}

是所有单次循环中所需计算时间的和。我们无法说

c_{1}

究竟是多少，因为他取决于计算机的计算速度，编译器或解释器将程序解释成可执行代码的时间，或者其他的一些因素。

代码有一点额外开销用来进行for循环（包括将guess初始化为0），结果可能返回-1。让我们来将这个额外开销的时间记为

c_{2}

, 他是个常量。因此，线性搜索最坏情况的总运行时间是

c_{1} \cdot n + c_{2}

。

正如我们讨论的，系数常量

c_{1}

和低阶项

c_{2}

无法告诉我们运行时间的增长速率。重要的是，线性搜索的最坏情况运行时间会随着数组大小

n

的增长而增长。我们使用符号

Θ (n)

来标识这个运行时间。它是希腊字母 "theta"，我们将之记作"big-Theta of

n

" 或者仅仅是 "Theta of

n

当我们说一个特定的运行时间是

Θ (n)

时，我们说，一旦

n

变得足够大，存在某些常量

k_{1}

、

k_{2}

，运行时间至少是

k_{1} \cdot n

，至多是

k_{2} \cdot n

。下面是如何思考

Θ (n)

当

n

很小时，我们不在乎运行时间

k_{1} \cdot n

比起

k_{2} \cdot n

谁更快。但是，一旦

n

变得足够大——在虚线上或右侧——运行时间必须处于

k_{1} \cdot n

和

k_{2} \cdot n

之间。只要这些常量

k_{1}

和

k_{2}

存在, 我们就说运行时间是

Θ (n)

。

我们并不限制 big-Θ符号中的

n

。我们可以使用任何函数，如

n^{2}

，

n \log_{2} n

，或者关于

n

的任何其他函数。下面是如何思考一些函数

f (n)

的运行时间

Θ (f (n))

一旦

n

足够大，运行时间处于

k_{1} \cdot f (n)

和

k_{2} \cdot f (n)

之间。

实际上，我们只是去掉了常量和低阶项。使用 big-Θ 标记的另一个优点是，我们不必担心使用的是哪些时间单位。例如，假设计算的运行时间为

6 n^{2} + 100 n + 300

秒。或者也可能是毫秒。当使用big-Θ 标记时，你不用管它。你也可以去掉系数和低阶项

100 n + 300

，你只需要说，运行时间是

Θ (n^{2})

。

当我们使用big-Θ符号时，我们说的是我们在运行时间上有一个 渐近紧约束 。"渐近"是因为它只对

n

起作用。"紧约束"，因为我们已经将运行时间约束在常量系数的上限和下限中。

本内容是达特茅斯计算机科学教授 Thomas Cormen 和 Devin Balkcom，与可汗学院的计算课程团队合作完成。内容获得许可 CC-BY-NC-SA。

想加入讨论吗？

排序方式:

尚无帖子。

你会英语吗？单击此处查看更多可汗学院英文版的讨论.