第一章 算法在计算机中的作用

1.1 算法

​ 算法(algorithm)：就是任何良定义的计算过程，该过程取某个值或值的集合作为输入并产生某个值或值的集合作为输出。这样算法就是把输入转换成输出的计算步骤的一个序列。

算法问题所共有的两个特征：

• 存在许多候选解，但绝大多数候选解都没有解决手头的问题。寻找一个真正的解或一个最好的解可能是一个很大的挑战。
• 存在实际应用。

​ 数据结构是一种存储和组织数据的方式，旨在便于访问和修改。没有一种单一的数据结构对所有用途均有效，所以重要的是知道几种数据结构的优势和局限。

1.2 作为一种技术的算法

​ 为求解相同问题而设计的不同算法在效率方面常常具有显著的差别。这些差别可能比由于硬件和软件造成的差别要重要得多。

​ 我们应该像计算机硬件一样把算法看成是一种技术。整个系统的性能不但依赖于选择快速的硬件而且还依赖于选择有效的算法。正如其他计算机技术正在快速推进一样，算法也在快速发展。

第二章 算法基础

2.1 插入排序

关千循环不变式，我们必须证明三条性质：

• 初始化：循环的第一次迭代之前，它为真。
• 保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。
• 终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助千证明算法是正确的。

{collapse}
{collapse-item label=“伪代码中的一些约定” open}

• 缩进表示块结构。我们的缩进风格也适用于if-else 语句气采用缩进来代替常规的块结构标志，如begin 和end 语句，可以大大提高代码的清晰性。

• while 、for 与 repeat-until 等循环结构以及if-else 等条件结构与C 、C ++ 、Java 、Python和Pascal 中的那些结构具有类似的解释气不像某些出现千C ++ 、Java 和Pascal 中的情况，本书中在退出循环后，循环计数器保持其值。当一个for 循环每次迭代增卫叮加其循环计数器时，我们使用关键词to。当一个for 循环每次迭代减少其循环计数器时，我们使用关键词 downto。当循环计数器以大千1 的一个量改变时，该改变量跟在可选关键词by 之后。

• 符号"//"表示该行后面部分是个注释。

• 形如 i=j=e 的多重赋值将表达式e 的值赋给变量 i 和 j。

• 变量（如1 、j 和key) 是局部于给定过程的。若无显式说明，我们不使用全局变量。

• 数组元素通过“数组名[下标]“这样的形式来访问。例如， A[i]表示数组A 的第i 个元素。记号”… "用于表示数组中值的一个范围，这样， A[l… j]表示A 的一个子数组，它包含 j个元素A[l], A[2], …, A[j] 。

• 复合数据通常被组织成对象，对象又由属性组成。我们使用许多面向对象编程语言中创建的句法来访问特定的属性：对象名后跟一个点再跟属性名。例如，数组可以看成是一个对象，它具有属性length, 表示数组包含多少元素，如A.length 就表示数组A 中的元素数目。

  • 我们把表示一个数组或对象的变量看做指向表示数组或对象的数据的一个指针。换句话说，在赋值y=x 后， x 和y 指向相同的对象。
  • 我们的属性记号可以“串联”。例如，假设属性f 本身是指向某种类型的具有属性g的对象的一个指针。那么记号x.f.g 被隐含地加括号成 (x.f).g 。换句话说，如果已经赋值 y=x.f，那么 x.f.g 与 y.g 相同。
  • 有时，一个指针根本不指向任何对象。这时，我们赋给它特殊值NIL 。

• 我们按值把参数传递给过程：被调用过程接收其参数自身的副本。如果它对某个参数赋值，调用过程看不到这种改变。当对象被传递时，指向表示对象数据的指针被复制，而对象的属性却未被复制。例如，如果x 是某个被调用过程的参数，在被调用过程中的赋值x=y 对调用过程是不可见的。然而，赋值x.f=3 却是可见的。类似地，数组通过指练习针来传递，结果指向数组的一个指针被传递，而不是整个数组，单个数组元素的改变对调用过程是可见的。

• 一个return 语旬立即将控制返回到调用过程的调用点。大多数return 语句也将一个值传递回调用者。我们的伪代码与许多编程语言不同，因为我们允许在单一的return 语句中返回多个值。

• 布尔运算符"and"和"or"都是短路的。也就是说，当求值表达式"x and y" 时，首先求值X 。如果x 求值为FALSE, 那么整个表达式不可能求值为TRUE, 所以不再求值y 。另外，如果x 求值为TRUE, 那么就必须求值y 以确定整个表达式的值。类似地，对表达式"x or y", 仅当x 求值为FALSE 时，才求值表达式y 。短路的运算符使我们能书写像"x != NIL and x. f=y"这样的布尔表达式，而不必担心当x 为NIL 时我们试图求值x.f将会发生什么情况。

• 关键词error 表示因为已被调用的过程情况不对而出现了一个错误。调用过程负责处理该错误，所以我们不用说明将采取什么行动。

2.2 分析算法

​ 一般来说，算法需要的时间与输入的规模同步增长，所以通常把一个程序的运行时间描述成其输入规模的函数。为此，我们必须更仔细地定义术语”运行时间”和互“输入规模"。

​ 输入规模的最佳概念依赖于研究的问题。对许多问题，如排序或计算离散傅里叶变换，最自然的量度是输入中的项数，例如，待排序数组的规模n 。对其他许多问题，如两个整数相乘，输入规模的最佳量度是用通常的二进制记号表示输入所需的总位数。有时，用两个数而不是一个数来描述输入规模可能更合适。例如，若某个算法的输入是一个图，则输入规模可以用该图中的顶点数和边数来描述。对于研究的每个问题，我们将指出所使用的输入规模量度。

​ 一个算法在特定输入上的运行时间是指执行的基本操作数或步数。定义”步”的概念以便尽量独立千机器是方便的。目前，让我们采纳以下观点，执行每行伪代码需要常量时间。虽然一行与另一行可能需要不同数量的时间，但是我们假定第i 行的每次执行需要时间C;’ 其中c, 是一个常量。这个观点与RAM 模型是一致的，并且也反映了伪代码在大多数真实计算机上如何实现。

最坏情况与平均情况分析

​ 最坏情况与平均情况分析即对规模为n 的任何输入，算法的最长运行时间。

• 一个算法的最坏情况运行时间给出了任何输入的运行时间的一个上界。知道了这个界，就能确保该算法绝不需要更长的时间。我们不必对运行时间做某种复杂的猜测并可以期望它不会变得更坏。
• 对某些算法，最坏情况经常出现。例如，当在数据库中检索一条特定信息时，若该信息不在数据库中出现，则检索算法的最坏情况会经常出现。在某些应用中，对缺失信息的检索可能是频繁的。
• "平均情况“往往与最坏情况大致一样差。

增长量级

​ 我们真正感兴趣的运行时间的增长率或增长量级。所以我们只考虑公式中最重要的项（例如， $an^2$ ), 因为当n 的值很大时，低阶项相对来说不太重要。我们也忽略最重要的项的常系数，因为对大的输入，在确定计算效率时常量因子不如增长率重要。
​ 如果一个算法的最坏情况运行时间具有比另一个算法更低的增长量级，那么我们通常认为前者比后者更有效。由于常量因子和低阶项，对千小的输入，运行时间具有较高增长量级的一个区幻算法与运行时间具有较低增长量级的另一个算法相比，其可能需要较少的时间。但是对足够大的输入，例如，一个 $O(n^2)$ 的算法在最坏情况下比另一个 $O(n^4)$ 的算法要运行得更快。

2.3 设计算法

1. 分治法

   分治法：将原问题分解为儿个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

   分治模式在每层递归时都有三个步骤：

   • 分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。
   • 解决这些子问题，递归地求解各子问题。然而，若子问题的规模足够小，则直接求解。
   • 合并这些子问题的解成原问题的解。

   归井排序算法完全遵循分治模式。直观上其操作如下：

   • 分解：分解待排序的n 个元素的序列成各具n/2 个元素的两个子序列。
   • 解决：使用归并排序递归地排序两个子序列。
   • 合并：合并两个已排序的子序列以产生已排序的答案。

2. 分析分治算法

   ​ 分治算法运行时间的递归式来自基本模式的三个步骤。如前所述，我们假设T(n) 是规模为n 的一个问题的运行时间。若问题规模足够小，如对某个常量c，$n \le c$ 则直接求解需要常量时间，我们将其写作 $O(1)$ 。假设把原问题分解成a 个子问题，每个子问题的规模是原问题的 1/b 。（对归并排序，a 和b 都为2, 然而，我们将看到在许多分治算法中，$a \ne b$ 。）为了求解一个规模为 n/b 的子问题，需要 $T(n/b)$ 的时间，所以需要$aT(n/b)$ 的时间来求解a 个子问题。如果分解问题成子问题需要时间 ,$D(n)$ 合并子问题的解成原问题的解需要时间C(n), 那么得到递归式：

   $$T(n)=\left\{\begin{array}{ll} \Theta(1) & \text { 若 } n \leqslant c \\ a T(n/b)+D(n)+C(n) & \text { 其他 } \end{array}\right.$$

第四章 分治策略

在分治策略中，我们递归地求解一个问题，在每层递归中应用如下三个步骤：

• 分解(Divide) 步骤将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
• 解决(Conquer) 步骤递归地求解出子问题。如果子问题的规模足够小，则停止递归，直接求解。
• 合井(Combine) 步骤将子问题的解组合成原问题的解。

​ 当子问题足够大，需要递归求解时，我们称之为递归情况(recursive case) 。当子问题变得足够小，不再需要递归时，我们说递归已经＂触底“，进入了基本情况(base case) 。，除了与原问题形式完全一样的规模更小的子问题外，还需要求解与原问题不完全一样的子问题。我们将这些子问题的求解看做合并步骤的一部分。

递归式

三种求解递归式的方法，即得出算法的"$\Theta$"或"O’渐近界的方法：

• 代入法：我们猜测一个界，然后用数学归纳法证明这个界是正确的。
• 递归树法：将递归式转换为一棵树，其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式。
• 主方法：可求解形如下面公式的递归式的界： $T(n) = a T(n/b)+f(n)$ 其中 $a \ge 1$, b > 1, f(n) 是一个给定的函数。这种形式的递归式很常见，它刻画了这样一个分治算法：生成a 个子问题，每个子间题的规模是原问题规模的1/b, 分解和合并步骤总共花费时间为 f(n) 。

4.1 最大子数组问题

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:

输入: [100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97]
输出: 8
解释: 在第8天（股票价格=81）的时候买入，在第11天（股票价格=106）的时候卖出，最大利润=106-11=43。
	 初始价格为第0天

问题变换

​ 考察每日价格变化，第 i 天的价格变化定义为第 i 天和第 i-1天的价格差，那么问题就转化为寻找该数组的和最大的非空连续子数组。我们称这样的连续子数组为最大子数组(maximum subarray) 。

[13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]

​ 只有当数组中包含负数时，最大子数组问题才有意义。如果所有数组元素都是非负的，最大子数组问题没有任何难度，因为整个数组的和肯定是最大的。

使用分治策略的求解方法

$A[low…high]$ 的任何连续子数组 $A[i...j]$ 所处的位置必然是以下三种情况之一：

• 完全位千子数组 $A[low...mid]$ 中，因此 $low \le i \le j \le mid$ 。
• 完全位于子数组 $A[mid+1...high]$ 中，因此 $mid \lt i \le j \le high$ 。
• 跨越了中点，因此 $low \le i \le mid \lt j \le high$。

​ 算法接收数组A 和下标low 、mid 和high 为输入，返回一个下标元组划定跨越中点的最大子数组的边界，并返回最大子数组中值的和。

FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
  left-sum = -oo
  sum = 0
  for i = mid downto low
    sum = sum + A[i]
    if sum > left-sum
      left-sum = sum
      max-left = i
  left-sum = -oo
  sum = 0
  for j = mid + 1 to high
    sum = sum + A[j]
    if sum > right-sum
      right-sum = sum
      max-right = j
  return (max-left, max-right, left-sum + right-sum)

求解最大子数组问题的分治算法：

FIND-MAXIMUM-SUBARRAY(A, low, high)
  if high == low
    return (low, high, A[low]) // base case: only one element
  else mid == (low + high) / 2
    (left-low, left-high, left-sum) = FIND-MAXIMUM-SUBARRAY(A, low, mid)
    (right-low, right-high, right-sum) = FIND-MAXIMUM-SUBARRAY(A, mid + 1, high)
    (cross-low, cross-high, cross-sum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)

    if left-sum >= right-sum and left-sum >= cross-sum
      return (left-low, left-high, left-sum)
    else if right-sum >= left-sum and right-sum >= cross-sum
      return (right-low, right-high, right-sum)
    else 
      return (cross-low, cross-high, cross-sum)

分治算法的分析

$T(n) = O(n lgn)$

4.2 矩阵乘法的Strassen 算法

若 $A=(a_{ij})$ 和 $B=(b_{ij})$ 是nXn 的方阵，则对i, j=1, 2, …, n, 定义乘积C= A•B 中的元素 $c_{ij}$ 为：

$ c_{ij} = \sum_{k=1}^n a_{ik} \cdot b_{kj}$

一个简单的分治算法

将A 、B 和C 均分解为4 个n/2 X n/2 的子矩阵：

$$A=\left[\begin{array}{ll} A_{11} & A_{12} \\ A_{21} & A_{22} \end{array}\right], \quad B=\left[\begin{array}{ll} B_{11} & B_{12} \\ B_{21} & B_{22} \end{array}\right], \quad C=\left[\begin{array}{ll} C_{11} & C_{12} \\ C_{21} & C_{22} \end{array}\right]$$

因此由 $C=A \cdot B$ 可得

$$\begin{array}{l} C_{11}=A_{11} \cdot B_{11}+A_{12} \cdot B_{21} \\ C_{12}=A_{11} \cdot B_{12}+A_{12} \cdot B_{22} \\ C_{21}=A_{21} \cdot B_{11}+A_{22} \cdot B_{21} \\ C_{22}=A_{21} \cdot B_{12}+A_{22} \cdot B_{22} \end{array}$$

Strassen 方法（比较抽象 P79）

4.3 用代入法求解递归式

代入法求解递归式分为两步：

• 猜测解的形式。
• 用数学归纳法求出解中的常数，并证明解是正确的。

4.4 用递归树方法求解递归式

​ 在递归树中，每个结点表示一个单一子问题的代价，子问题对应某次递归函数调用。我们将树中每层中的代价求和，得到每层代价，然后将所有层的代价求和，得到所有层次的递归调用的总代价。然后即可用代入法来验证猜测是否正确。

4.5 用主方法求解递归式

可求解形如下面公式的递归式的界： $T(n) = a T(n/b)+f(n)$ 其中 $a \ge 1$, b > 1是常数, f(n) 是一个渐进正函数。

1. 若对某个常数 $\varepsilon>0$ 有 $f(n)=O\left(n^{\log _{b} a-c}\right)$ , 则 $T(n)=\Theta\left(n^{\log _{b} a}\right) $。
2. 若 $ f(n)=\Theta\left(n^{\log _{b^{b}} a}\right) $, 则 $T(n)=\Theta\left(n^{\log _{b} a} \lg n\right)$ 。
3. 若对某个常数 $\varepsilon>0$ 有 $f(n)=\Omega\left(n^{\log _{b} a+c}\right)$ , 且对某个常数 c<1 和所有足够大的 n 有 $a f(n / b) \leqslant c f(n) $, 则 $T(n)=\Theta(f(n)) $。