算法复杂度详解

【算法 1】

sum = 0
k = 0 //数组索引
While k < n do
    sum = sum + a[k]
    k = k + 1
EndWhile

现在来计算下面算法 1 所需的步数。该算法的组成包括：第 1 行和第 2 行中的两个语句，它们各执行一次；第 4 行和第 5 行这两个语句出现在循环中，每次循环迭代时它们也各执行一次。

前面介绍过，因为第 1 行和第 2 行的语句执行的是基本操作，所以可以将它们组合在一起，计为 1 个基本操作，在此可称之为【操作 A】。

另外，因为循环中的两个语句都是在常量时间内执行的，与 n 的大小无关，所以它们也是基本操作。由于循环体仅包含基本操作，算法执行循环的单次迭代所需的时间量也是恒定的，不依赖于 n 的大小。这意味着可以将每个循环迭代计算为一个基本操作。这个操作可称之为【操作 B】。

不管 n 有多大，操作 A 只执行一次。每次循环迭代时，操作 B 执行一次。因为循环重复了 n 次，操作 B 也就被执行了 n 次。因此，该算法操作执行的总次数是 1+n。例如，当 n=10 时，执行了 11 个操作；当 n=1000 时，执行了 1001 个操作；当 n= 10 000 时，执行的操作次数就是 10 001。请注意，随着 n 变大，1 就变得微不足道，并且执行的操作次数大约为 n。因此可以说，该算法所需的执行时间与 n 成正比，也就是与要处理的输入集合的大小 n 呈正相关。

还可以通过另外一种方式来看待算法 1，并确定它需要多少操作。要对数组中的值求和，关键操作就是将每个值添加到累加求和的变量上，该操作发生在第 4 行，有多少次循环迭代，就有多少次数组值的相加。

因此，只需通过计算数组元素的相加次数，也可以获得相同的结果。事实证明，对于大多数算法来说，只需要识别和计算一个或两个对解决问题至关重要的基本操作即可。例如，在许多数组搜索和排序算法中，只要计算数组元素之间的比较次数就足够了。

以上所讨论的数组求和算法分析起来特别简单，因为它对给定大小的所有输入集执行相同的工作量。

但并不是所有算法均如此。例如，本章前面介绍的线性搜索算法，它搜索一个包含值的数组，寻找匹配搜索关键字的值。可以将关键字称之为 X。算法的输入是数组的大小 n 值和关键字 X 值。算法的输出是被找到的值所在的数组位置的下标，或者，如果确定循环控制变量已经大于最后一个数组元素的下标，则可以提示没有找到。

形式上，该问题可以这样描述：

• INPUT：大小为 n 的整数数组 a[]，以及整数 X。
• SIZE OF INPUT：输入的数组元素的个数 n。
• OUTPUT：一个整数 k，k 的取值范围为 0≤k≤n-1，使得 a[k] = X 或 k = n。

以下显示的是算法 2，它使用了线性搜索算法来解决该问题。

【算法 2】

k = 0
While k < n and a [k]≠X do
    k = k + 1
End While

该算法从一端开始，依次搜索数组。该算法一旦遇到 X 就停止，但如果 X 不在数组中，则会搜索整个数组。该算法有可能在进行一次比较之后就会停止（X 在进行第一个数组元素的匹配时即被发现)，也有可能一直不停，直至它进行了 n 次比较（X 在最后一个数组位置被发现或并不在数组中）。

实际上，该算法可能会执行 m 次比较，其中 m 可以是从 1 到 n 的任何值。由此可见，该算法对同样大小的不同输入可能需要执行不同次数的操作，在这种情况下，要衡量算法的效率，往往需要对大小为 n 的输入完成最大量的工作，这就是所谓的通过其最坏情况复杂度函数来衡量算法。

算法最坏复杂度

算法的最坏情况复杂度函数（f(n)）是它在大小为 n 的输入上完成所需的最大工作量时执行的步骤数。它给出了算法解决 n 个实例的问题所用的最长时间的指示，并且是在寻求性能保证时的一个很好的衡量指标。

现在来确定本章前面介绍的二分搜索的最坏情况下的复杂度。这个算法用来在一个按升序排序的数组中查找项目 X。当在数组中找不到 X 时，就会发生最坏的情况。在这种情况下，可以看到算法将执行 L+1 个步骤，其中 L 是循环迭代的次数。

以下显示的就是二分搜索算法的伪代码，它可以搜索包含 n 个元素的数组。

【算法 3】

first = 0
last = n - 1 //n-1是数组最后一个元素的下标
found = false
position = -1
While found is not true and first <= last
    middle = (first + last) / 2
    If a[middle] = X
        found = true
        position = middle
    Else if a[middle] > X
        last = middle - 1
    Else
        first = middle + 1
    End If
End While
//当循环终止时，position 保存的下标正是匹配X值的元素的下标
//如果未找到匹配值，则 position 保存的值为 -1

该算法由一些变量的初始化和一个循环组成。初始化需要的时间是恒定的，因此可以认为是 1 个基本操作。同样，循环的每次迭代都是一个基本的步骤，因为增加数组中的元素数量并不会增加单次循环所需的时间量。这意味着二分搜索所需的步数为 L+1。现在，L 大约等于 log₂n 的整数部分，即以 2 为底的 n 的对数。

要理解这一点，请注意要搜索的数组的大小刚开始是 n，每次迭代之后，要搜索的数组的大小就只剩下大约一半。由于每个循环迭代至多执行两次比较，所以二分搜索需要执行的比较总次数就是 2log₂n。于是可以将该查找总结为：在最坏情况下，二分搜索需要的时间与 log₂n 成正比。

现在来看一看另外一个算法，以确定其最坏情况下的复杂度。该算法要解决的计算问题是将一组 n 个整数按升序排列：

1. INPUT：n 个整数的数组 a[]。
2. SIZE OF INPUT：输入的数组元素的个数 n。
3. OUTPUT：重新排序后的数组 a[]，使 a[0]≤a[1]≤…≤a[n-l]。

以下将使用的算法是选择排序算法的修改版。这个版本扫描最大的元素（而不是最小的），并在每趟排序后将其移动到最后。

【算法 4】

For (k = n-1; k> 1; k--)
    // a[0..k]是余下需要排序的部分
    Determine position p of largest entry in a[0..k]
        Swap a[p] with a[k]
End For

为了分析该算法的复杂度，不妨从确定在对 n 个元素的数组进行排序时需要进行比较的数组元素数量开始。这些比较在步骤 3 中进行。

步骤 3 显然不是一个基本步骤，因为它需要的时间与 k 成比例，而k则会随着循环的每次迭代而发生变化。为了更好地了解到底发生了什么，不妨使用基本操作重新描述第 3 步：

INPUT：包含k + 1个元素的数组a[0..k]。
SIZE OF INPUT：数组元素的个数k + 1。
p = 0    //数组未排序部分中最大值的位置
For (m = 1; m < k; m ++)
    If a[m] > a[p] Then
        p = m
    End if
End For

现在可以看到，第 4〜8 行的循环迭代了 k 次，而第 5 行在每次迭代时都进行了一次比较，因此这个算法需要在数组元素之间进行 k 次比较。

现在返回到主排序算法，可以发现，从第 4 行开始，到第 8 行结束的循环将进行 n-1 次迭代。对于范围在 n-1 和 1 之间的 k 值，每个 k 值都会迭代一次。在第一次迭代时，k 等于 n-1，所以，正如上面 4 行到 8 行所分析的那样，步骤 3 在数组元素之间执行 n-1 次比较；在第二次迭代中，k 等于 n-2，所以步骤 3 执行 n-2 次比较。这样一直持续到最后一次迭代时 k 等于 1，步骤 3 执行 1 次比较。

综上所述，其结果计算如下：

• k = n-1：步骤 3 执行 n-1 次比较；
• k = n-2：步骤 3 执行 n-2 次比较；
• k = 1：步骤 3 执行 1 次比较。

归纳起来，于是就可以这样说：对于从 n-1 到 1 的每个 k 值，在第 k 次迭代中，第 3 行上的步骤将执行 k 次比较。

因此，这个简单的排序算法进行比较的总次数就可以由以下表达式获得。

1+2 + 3 +…+(n-1)=(n-1)n/2

如果 n 值比较大，那么这个表达式的结果非常接近于 n²/2。所以可以得出结论说：在最坏的情况下，选择排序所需的时间与 n² 成正比。

平均情况下的复杂度

当然，最坏情况下的复杂度，并不能很准确地说明算法在实际情况下的表现如何，因为在实际环境中最坏情况的出现可能是很少见的。一般情况下，程序员更感兴趣的是确定典型或平均情况下的复杂度。

当我们知道实际环境中可能发生的不同输入的相对频率时，即可使用平均情况复杂度函数。平均情况复杂度函数使用这些频率来形成在每个输入上执行的步骤数的加权平均值。不幸的是，虽然它可以很好地衡量算法的预期性能，但是可能很难获得对输入频率的精确估计。

渐近复杂度与大O表示法

要比较解决问题的两种算法 F 和 G，可以通过比较它们的复杂度函数来进行。更具体地来说，如果 f(n) 和 g(n) 是两种算法的复杂度函数，则可以通过观察当 n 变大时，f(n)/g(n) 比例值的变化来比较这两种算法。如果比例值趋向某个极限，那么它就很好理解。现在来看几个具体的示例，当然，还是需要假设 f(n)≥1、g(n)≥1 并且所有 (n)≥1。

f(n) = 3n² + 5n 并且 g(n) = n²。在这种情况下：

也就是说，当 n 变大时，f(n)/g(n) 的值越来越接近于 3。这意味着对于非常大的输入大小，F 执行的基本操作数是 G 的 3 倍。但是，由于这两种算法的性能区别只有一个常数因子，所以，可以认为它们在效率上是等同的。

f(n) = 3n² + 5n 并且 g(n)=100n。在这种情况下：

在这里，当 n 变大时，f(n)/g(n) 的值变得越来越大。这意味着，如果输入较大，那么 F 算法执行的工作量要大于 G 算法，这表示 G 算法对于较大的输入更有优势。

f(n) = 3n² + 5n 并且 g(n) = n³。在这种情况下：

 

这意味着，如果输入较大，那么 G 算法执行的工作量要大于 F 算法，这表示 F 算法的效率更高。

一般来说，可以通过观察当 n 变大时，f(n)/g(n) 比例值发生的变化来比较两个复杂度函数 f(n) 和 g(n)。虽然从这个比例值的极限来看问题，有助于比较两种算法，但是却不能认为这样的极限总会存在。

事实证明，我们并不一定要通过极限才能从这个比例中获得有用的信息。如果可以找到一个正值的常数 K，那么对比较这两个复杂函数也是很有用的。正常数 K 的公式如下：

如果能做到这一点，就意味着对于较大输入的问题，算法F并不会比 KXG 差。在这种情况下，就可以说 f(n) 在 O(g(n)) 中。定义 f(n) 在 O(g(n)) 中的条件经常按如下形式编写：

证明 f(n) 在 O(g(n)) 中通常是很简单的。可以观察 f(n)/g(n) 的比例值，并试图找出一个正常数 K，使得对于所有 n≥1 都有 f(n)/g(n)≥K。例如，要证明 3n² + 5n 在 O(n²) 中，可以观察以下比例值，并且发现 5/n 在所有 n≥1 时其最大值为 5，所以 3+5/n≤8。因此，对于 K = 8，f(n)/g(n) ≥K。

要证明 f(n) 不在 O(g(n)) 中，需要证明无法找到一个正常数 K 满足对于所有 n>1 都有 f(n)/g(n)≤K。例如，函数 3n² + 5n 就不在 O(n) 中，因为没有常数 K 可以满足：

 

虽然 "大 O" 表示法是为函数定义的，但是该表示法和术语也可用于表示算法和计算问题。因此，如果 F 的最坏情况复杂度函数 f(n) 在 g(n) 的大 O 中，那么就可以说算法 F 在某些函数 g(n) 的 O(g(n)) 中。相应地，数组的顺序搜索是在 O(n) 中，而二分搜索则是在 O(log₂n) 中。

类似地，如果存在针对某个问题的算法，其最坏情况复杂度函数是在 O(g(n)) 中，那么该计算问题也可以说是在 O(g(n)) 中。因此，对数组排序的问题在 O(n²) 中，而搜索排序数 组的问题则在 O(log₂n) 中。

如果 g(n) 是一个函数，那么 O(g(n)) 可以被视为一个增长不如 g(n) 快的函数集合。这些集合被称为复杂度类，它们中有几个是非常重要的，足以获得特定的名称。以下按照它们增长的数量级列表并进行解释：

• O(1)：如果存在一个常数 K> 0 使得 f(n)≤K（对于所有 n≥1），则函数 f(n) 在该类中。如果某个算法的最坏情况下的复杂度函数在这个类中，则称该算法运行在常数时间中。
• O(log₂n)：该类中的算法运行在对数时间。由于log n 的增长速度比n慢得多，所以问题规模的巨大增加将导致算法的运行时间只有很小的增加。这种复杂度是搜索问题的特征，其每个基本操作就剔除了一半的搜索空间。二分搜索算法就是在这个类中。
• O(n)：该类中的算法运行在线性时间。问题大小的任何增加都将导致算法的运行时间成比例地增加。这种复杂度是诸如顺序搜索之类的算法的特征，它们在其输入上进行单次或恒定次数的遍历。
• O(nlog₂n)：该类中的算法运行在线性对数时间。问题大小的增加仅导致算法的运行时间稍微增加。快速排序排序算法的复杂度就在该类中。
• O(n²)：该类中的算法运行在平方时间。这种性能是使用两个嵌套循环对输入数据进行多趟排序的算法的特征。问题大小的增加将导致算法运行时间的极大增加。冒泡排序、选择排序和快速排序这些算法的最坏情况下的复杂度函数都属于该类。