I-Algorithms

📘 分析算法

介绍

分析算法的结果主要用于预测算法需要的资源，例如内存、通信带宽、计算机硬件，但是通常最需要度量的是计算时间。为了分析算法的运行时间，需要有一个实现技术的模型，用于描述所用资源及其代价的模型。这里假定通用的单处理器计算模型RAM(random-access machine)作为实现技术，在RAM模型中，指令一条一条地执行，没有并发操作。

说明

通用的单处理器计算模型RAM在这里不指代计算机中的高速缓存或虚拟内存等，这些现代存储技术可能对于真实计算机上运行的真实程序影响重大。

RAM模型包含计算机常见的指令：算术指令（+、-、*、/、%等）、数据移动指令（存储、复制、装入等）、控制指令（条件、子程序调用与返回）等，每条这样的指令所需的时间都为常量。RAM模型中存在一些灰色区域（包含了一些未列出的指令），例如计算或者相对典型的，计算可能需要若干条指令才能完成，而计算则相对简单一些，只需要将数据左移位即可，当足够小的情况下，可以将看作一个常量时间的操作。

采用RAM模型分析算法的运行时间，需要的数学工具可能包括组合学、概率论、代数技巧以及识别公式中最有意义的项。

说明

识别公式中最有意义的项，个人理解为识别公式中占主导地位的项，例如当足够大时，中决定数量级别的项是。

插入排序算法的分析

一般来说，算法需要的运行时间与输入规模同步增长，通常情况下。

说明

输入规模视情况而定，例如排序或计算离散傅里叶变换，那么量度是输入的项数。而对于图而言，输入规模可用图中的顶点数和边数来描述。对于研究的每一个问题，都需要指出使用的输入规模量度。

在程序运行中，运行每一行代码需要常量时间（这里包括子程序调用，只是子程序调用需要更大的常量时间而已），注释是不可执行的语句，因此不需要花费时间。对插入排序进行运行总时间统计：

function insertionSort (originalArray, customComparator) {
  // 1
  const array = [...originalArray]
  // 2
  let currentElement, preIndex

  // 3
  for (let i = 1; i < array.length; i++) {
    // 4
    preIndex = i - 1
    // 当前需要排序的元素（第一个元素默认已经排好序）
    // 5
    currentElement = array[i]
    // 判断前一个元素是否大于当前元素，如果是则前一个元素往后移
    // 直到不存在前一个元素或者前一个元素小于当前元素，则停止移动
    // 6
    while (preIndex >= 0 && array[preIndex] > currentElement) {
      // 7
      array[preIndex + 1] = array[preIndex--]
    }
    // 将当前排序元素插入到移动后的位置
    // 8
    array[preIndex + 1] = currentElement
  }

  // 9
  return array
}

以上标注的数字代表程序运行指令对应的行（需要注意去除了自定义比较功能），假定第行的程序每次执行需要常量时间，那么每行运行的代价和次数如下表所示：

指令序号 运行代价 运行次数
1 1
2 1
3 n
4 n-1
5 n-1
6

7

8 n-1
9 1

说明

注意循环头的执行次数比循环体多一次，用于判断循环退出条件。图中的表示程序运行在值时while循环所需要执行的次数，例如考虑最佳情况，待插入的元素在循环不变式中是最大的，那么while循环只需要执行一次（循环一次都不满足），如果考虑最坏情况，待插入的元素在循环不变式中是最小的，那么运行值时，while循环需要执行次，因此用表示循环不确定的次数。

插入排序算法所需要的总代价如下：

考虑最佳情况，当时：

可以把上述公式表示为：

考虑最坏情况，当时：

可以把上述公式表示为：

最坏情况分析

在上面的分析中，我们考虑了最佳情况和最坏情况，但是在实际中我们往往更应该考虑最坏情况：

  • 最坏情况给出了输入规模对应的运行时间上界，可以期望它不会变的更差。
  • 最坏情况经常出现。
  • 平均情况往往与最坏情况一样差，例如考虑上述插入排序，当时，仍然是的二次函数。

增长量级

对于，其中的、、其实和代价息息相关，但是这种表述方式显然将代价进行了忽略。为了进行再简化抽象，我们将关注算法运行时间的增长率和正常量级，这里我们需要具备识别公式中最有意义的项的能力，即当足够大时，占主导地位的是，而低阶项可以被忽略，因此在快速排序中最坏情况的增长量级和最重要项的因子相关，因此我们可以将运行时间简化，记为。同时如果一个算法的最坏情况运行时间具有比另一个算法更低的增长量级，我们通常认为前者比后者更有效。

小结

主要分析了插入排序的运行时间。分析运行时间引入了记号，该记号用于标记算法运行时间与输入规模的关系。是输入规模为的一个问题的运行代价，如果对于某个常数有，那么求解只需要常量时间，我们记为。如果，那么求解需要时间为。

← 📙 分析算法习题 →