Design and Analysis of Algorithms 算法设计与分析

1.算法概述及复杂性理论

1.1 问题

1.1.1算法复杂度

  1. 时间频度（语句频度）

    ​ 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。算法的时间复杂度是指执行算法所需要的计算工作量。

  2. 时间复杂度

    ​ 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。

​ 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),存在一个正常数c使得fn*c>=T(n)恒成立。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

​ 在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n^2+3n+4与T(n)=4n^2+2n+1它们的频度不同，但时间复杂度相同，都为O(n^2)。

​ 按数量级递增排列，常见的时间复杂度有：

  • 常数阶O(1),对数阶O(log2n)(以2为底n的对数，下同),线性阶O(n),
  • 线性对数阶O(nlog2n),平方阶O(n2) 立方阶O(n3) ,…，
  • k次方阶O(nk) ,指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

  1. 空间复杂度

    • 与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作：S(n)=O(f(n))
    • 算法执行期间所需要的存储空间包括3个部分：
      • 算法程序所占的空间；
      • 输入的初始数据所占的存储空间；
      • 算法执行过程中所需要的额外空间。

1.1.2 P、NP、NPC、NPH问题的区别和联系

  • 时间复杂度

    ​ 时间复杂度描述了当输入规模变大时，程序运行时间的变化程度，通常使用O来表示。比如单层循环的时间复杂度为O(n)，也就是说程序运行的时间随着输入规模的增大线性增长，两层循环的时间复杂度为O(n2)，快速排序的时间复杂度为O(nlogn)，使用穷举法解决旅行商问题的时间复杂度为O(n!)。时间复杂度根据变化速率的快慢可以分为两类：1、多项式级的时间复杂度，如O(1),O(n),O(na),O(logn)等；2、非多项式级时间复杂度，如O(an),O(n!)等。当我们使用计算机解决一个问题时，我们要尽可能地找到一个具有多项式级时间复杂度的算法，非多项式级时间复杂度的算法一般运行时间较长，当输入数据规模较大时很难被接收。

    • P类问题

      • 如果一个问题能找到在多项式时间内解决它的算法，那么我们说该问题是P类问题。P是多项式（Polynomial）的第一个字母。比如排序问题就是一个P问题，因为我们可以找到一个时间复杂度为O(n2)的冒泡排序算法。

    • NP问题

      • 有些问题比较复杂，如旅行商问题，汉密尔顿回路问题等，当我们使用暴力搜索时，此类问题的时间复杂度为O(n!)，看起来很难找到一个能在多项式时间内解决该问题的算法，而如果别人给了我一个解，我可以很快地验证该解是不是问题的正确答案。比如在汉密尔顿回路问题中，我想验证一条路径是否正确，则验证路径是否正确的时间复杂度为O(n)，为多项式级的时间复杂度。所以，如果我们可以在多项式级的时间内验证一个问题解的正确性，那么我们说该问题是NP问题，也就是说直接找NP问题的一个解可能很慢，当验证NP问题的解却很快。前面提到的汉密尔顿回路就是一个NP问题。NP问题不是“非P问题”，而是非确定性多项式（nondeterministic polynomial）问题。

    • NPC问题

      • 从上面的介绍我们知道，所以P问题都是NP问题，因为能在多项式时间内解决的问题也能够在多项式时间内验证解的正确性。那么我们还想知道是否所有的NP问题都是P问题，这就是著名的“P对NP问题（P=NP?）”。在2000年美国的Clay数学研究所公布的七个千年数学难题中，P对NP问题位居榜首，可见解决该问题的难度。由于直接证明P对NP问题过于复杂，人们引入了另一类问题–NPC问题（NP -complete，NP-完全问题）。

      • 归约：

        ​ 在介绍NPC问题之前，需要先了解归约的概念。假设有两个问题A和B，对问题A的输入a经过某种规则转换为对问题B的输入b，而A(a)和B(b)的结果相同，也就是说我们可以将求解A问题转换为求解B问题，或者说可以用解决问题B的方法解决问题A，那我们称A可以归约（reducibility，或“约化”）到B。比如问题A为“求解一元一次方程的解”，问题B为“求解一元二次方程的解”，那么我们就可以将问题A归约到问题B，因为求解一元二次方程解的方法可以被用来求解一元一次方程的解。有一点需要注意，问题A不会难于问题B，也就是说，A要归约到更难的问题（时间复杂度更高）。除此之外，归约还具有传递性，如果A可以归约到B，B可以归约到C，那么A可以归约到C。

      • NPC问题

        • 当一个问题归约到另一个问题时，问题的复杂度变高了，问题的适用范围也更广了。通过对问题的不断归约，我们可以得到更复杂、适用范围更广的问题来替代简单但使用范围小的问题。那么我们就有一个想法 ：是否可以将若干相对不那么复杂NP问题不断归约，从而得到一个最难的“超级NP问题”，所有的NP问题都可以归约到这个“超级NP问题”，只要解决了这个“超级NP问题”，那么也就意味着所有NP问题都可以被解决。事实上，存在这样的一类“超级NP问题”，这也就是我们所说的NPC问题。NPC问题的定义如下：如果一个问题Q，它满足以下两条性质： (1). Q是NP问题 (2). 任一NP问题都可在多项式时间内归约到问题Q 那么我们说问题Q是NPC问题。 Stephen Cook是NPC理论的奠基人，而Richard Karp则证明了组合优化中的大多数经典问题（背包问题、覆盖问题、匹配问题、分区问题、路径问题、调度问题等）都是NPC问题。如果我们给NPC问题找到了一个多项式时间复杂度的算法，那么也就意味着我们给所有的NP问题找到了多项式时间复杂度的算法，从而NP=P，因为P=NP，所以“P对NP问题”就可以被解决。比如背包问题是NPC问题，如果我们给背包问题找到了一个多项式时间复杂度的算法，那么就证明了P=NP，但给NPC问题找一个多项式时间复杂度的算法太难了，所以现在人们普遍相信P≠NP。

    • NPH问题

      • 上面我们介绍了NPC问题需要满足两条性质，当一个问题仅满足性质(2)，而不满足性质(1)时，我们说该问题时NPH问题（NP-hard，NP-难问题）。

    • 4类问题的联系

      ​ img

      可以看到P类问题是NP问题，NPC问题是NP问题中最难的问题，NPH问题至少与NPC问题一样难。

1.2 算法的概念

1.3 算法正确性

image-20200225141236200

  • 正确的算法

    • 对任意一个输入，都有正确的输出

  • 循环不变量

    • 与程序变量有关的一个语句，它在循环刚开始前，以及在循环的每个迭代执行后为真，特别是在循环结束后，仍然为真。

  • 插入排序的循环不变量

    • 在for循环第j个迭代执行前，子数组A[1,…,j-1]由最初A[1,…,j-1]中的元素构成，不过现在是有序的

  • 利用循环不变量证明算法的正确性

    • 寻找到循环不变量，即某个特性Lj，然后证明循环不变量为真Lj(j = 1,…,n)，然后利用类似数学归纳法的证明方法：
        1. 初始步：在循环的迭代开始前，L1为真；
        1. 归纳步：如果在循环的第j个迭代前，Lj-1为真，则在循环的第j+1个迭代前，Lj为真；
        1. 终止步：当循环终止时，Ln为真。
    • 插入排序的算法正确性证明

1.4 算法的效率

  • 算法效率(Efficiency)的分析，指的是算法求解一个问题所需要的时间和空间。

  • 时间资源和空间资源

  • 计算模型

    • Turing机，以及RAM（随机存储器）等

  • 算法时间资源的估算

    • 算法执行基本运算（或步数）的数目
  • 度量一个算法运行时间的三种方式：
    • 最好情形时间复杂度
    • 最坏情形时间复杂度
    • 平均情形时间复杂度
  • 三种情形比较
    • 最坏情形是任何规模为n的问题实例运行时间的上界，即任何规模为n的实例，其运行时间都不会超过最坏情形的运行时间。知道最坏情形运行时间后，我们就知道算法最差到什么程度。
    • 对某些算法，最坏情形经常发生。例如在某个数据库中查询不存在的某条数据就是查询算法的最坏情形。
    • 平均情形有时跟最坏情形差不多。
  • 算法的时间复杂度取决于主要项
  • 算法的效率主要取决于算法本身，与计算模型（例如计算机）无关，这样可以通过分析算法的运行时间，从而比较出算法之间的快慢。

1.5 问题的下界

  • 问题的下界（Lower Bounds），即任何一种算法解决一个问题所必须的最小运行时间。
  • 加顶一个问题的下界为F(n),而当前解决该问题的最好算法为A，其最坏情形时间复杂度为W(n)，如果F(n) = W(n) ，则A是最优算法。

2.算法分析方法

2.1 概率分析

  • 平均案例分析决定算法运行平均时间。
  • 期望运行时间往往是所有n个实例运行时间的平均。
  • 平均情况分析往往需要对事件的先验概率有一个较好估计。
  • 精确的时间复杂度分析往往耗时耗力。
  • 如果你对平均情况更为感兴趣，那么可以考虑使用概率分析，并在这一过程中，认为每种情况都等可能的发生。

    3.递归

    3.1.算法思想

  • 递归(Recurrence)：计算机、数学、运筹等领域经常使用的最强大的解决问题的方法之一，它用一种简单的方式来解决那些用其他方法解起来可能很复杂的问题，也就是说有些问题用递归算法来求解，则变得简单，而且容易理解。

  • 递归的基本思想：把一个问题划分为一个或多个规模更小的子问题，然后用同样的方法解规模更小的子问题。

  • 递归算法的基本设计步骤
    • 找到问题的初始条件（递归出口），即当问题规模小到某个值时，该问题变得很简单，能够直接求解。
    • 设计一个策略，用于将一个问题划分为一个或多个一步步接近递归出口的相似的规模更小的子问题。
    • 将所解决的各个小问题的解组合起来，即可得到原问题的解。
  • 设计递归算法时需注意以下几个问题：
    • 如何使定义的问题规模逐步缩小，而且始终保持同一问题类型？
    • 每个递归求解的问题其规模如何缩小？
    • 多大规模的问题可作为递归出口？
    • 随着问题规模的缩小，能到达递归出口吗？

  • Hanoi问题

    • 递归算法来求解圆盘搬动问题，其详细过程如下 (1) 将前个圆盘从A柱借助于C柱搬到B柱； (2) 将最后一个圆盘直接从A柱搬到C柱； (3) 将个圆盘从B柱借助于A柱搬到C柱。

      ​ Hanoi(n, A, B, C) 1 if n=1 then move(1, A, C) 2 else 3 Hanoi(n-1, A, C, B) 4 move(n, A, C) 5 Hanoi(n-1, B, A, C)

    • 时间复杂度分析

      • ​ \(T(n)=\left\{ \begin{aligned} O(1)　　　if 　n = 1\\2*T(n-1) + 1　if　n>1\end{aligned} \right.\)

3.2选择排序

  • 基本思想就像排列你手中的扑克牌一样：

    • 把所有牌摊开，放在桌上，伸出你的左手，开始为空，准备拿牌；

    • 将桌上最小的牌拾起，并把它插到左手所握牌的最右边。

    • 重复步骤（2），直到桌上所有牌都拿在你的左手上，此时左手上所握的牌便是排好序的牌。

      SelectSort1(i) 1 if i≥n then return 0 2 else 3 k = i 4 for j = i+1 to n do 5 if A[j] < A[k] then 6 k = j 7 if k≠i then A[i] ↔ A[k] 8 SelectSort1(i+1)

  • 递归方程

    ​ \(T(n)=\left\{ \begin{aligned} O(1)　　　　　　　　if 　n = 1\\ T(n-1) + (n-1)　if　n>1\end{aligned} \right.\)

3.3生成排序

  • 问题是生成{1,2,…,n}的所有n!个排列
  • 想法 1: 固定位置放元素 假设我们能够生成 n-1个元素的所有排列，我们可以得到 如下算法：
    • 生成元素{2,3,…,n}的所有排列，并且将元素1放到每个 排列的开头；
    • 接着，生成元素{1,3,…,n}的所有排列，并将数字2放到 每个排列的开头；
    • 重复这个过程，直到元素{2,3,…,n-1}的所有排列都产生， 并将元素n放到每个排列的开头。

GeneratingPerm1() 1 for j←1 to n do 2 P[j] ←j 3 Perm1(1)

Perm1(m) 1 if m=n then output P[1..n] 2 else 3 for j←m to n do 4 P[j] ↔ P[m] 5 Perm1(m+1) 6 P[j] ↔P[m]

  • 时间复杂度分析

    ​ \(T(n)=\left\{ \begin{aligned} O(1)　　　 if 　n = 1\\ nT(n - 1) + n　if　n>1\end{aligned} \right.\)

  • 想法 2：固定元素找位置

    • 首先，我们把 n 放在的位置P[1]上，并且用子数组P[2..n] 来产生前n-1个数的排列；
    • 接着，我们将 n 放在P[2]上，并且用子数组P[1]和P[3..n] 来产生前n-1个数的排列；
    • 然后，我们将 n 放在P[3]上，并且用子数组P[1..2]和 P[4..n]来产生前n-1个数的排列；
    • 重复上述过程直到我们将 n 放在P[n]上，并且用子数组 P[1..n]来产生前n-1个数的排列。

GeneratingPerm2() 1 for j←1 to n do 2 P[j] ←0 3 Perm2(n)

Perm2(m) 1 if m=0 then output P[1..n] 2 else 3 for j←1 to n do 4 if P[j]=0 then 5 P[j] ←m 6 Perm2(m-1) 7 P[j] ←0

  • 时间复杂度分析

​ \(T(n)=\left\{ \begin{aligned} O(1)　　　　if 　n = 1\\ nT(n - 1) + n　if　n>1\end{aligned} \right.\)

3.4 递归方程的求解

  • 算法运行时间复杂度主要由关于问题规模的高阶项决定，因此当我们实际描述并解决一个递归方程时，我们可以忽略递归出口、顶和底等技术细节。

    \[T(n)=\left\{ \begin{aligned} O(1)　　　　if 　n = 1\\T(n / 2) + T(n / 2) + O(n)　if　n>1\end{aligned} \right.\]

    ​ 忽略递归出口、顶和底

    \[T(n) = 2T(n/2) + O(n)\]

  • 公式法

    • 对于下列形式的递归方程 \(T(n) = aT(n/b)+f (n)\) 其中a ≥ 1，b > 1是常数， f (n)是一个渐近正函数，可以使用公式法(Master Method)方便快捷地求得递归方程的解。
    • 将一个规模为n的问题划分为a个规模为n/b的子问题，其中a和b为正常数。分别递归地解决a个子问题，解每个子问题所需时间为T (n/b)。划分原问题和合并子问题的解所需要的时间由f (n)决定。
    • T(n)有以下三种情形的渐进界：
      • 情形1
        • if f(n) = O(nlogba - $\varepsilon$), for some constant $\varepsilon$ > 0,then T(n) = O(nlogba)
      • 情形2
        • if f(n) = O(nlogba), then T(n) = O(nlogbalg n)
      • 情形3
        • if f(n) = $\Omega$(nlogba + $\varepsilon$), for some constant $\varepsilon$ > 0,and if af(n/b)=<cf(n),for some c < 1 and all sufficiently large , then T(n) = O(f(n))
      • 在以上每一种情形中，我们都把函数 f (n) 与 nlogba  作比较。直观地，递归解是由两个函数中数量级较大的一个决定的。
        • 对于情形1， nlogba 比较大, 因此解为 T(n) = O(nlogba ) .
        • 对于情形3， f (n)比较大, 因此解为T (n) = Θ(f(n))
        • 对于情形2, 两个函数同样大小，我们乘上一对数因子，得到 解 T(n) = O(nlogba lg n)

4.分治（上）

4.2 二分搜索

  • 该问题的规模缩小到一定的程度就可以容易地解决；
  • 该问题可以分解为若干个规模较小的相同问题;
  • 分解出的子问题的解可以合并为原问题的解；
  • 分解出的各个子问题是相互独立的。

5.分治（下）

5.1 覆盖残缺棋盘

  • A是一个n×n的棋盘，n为2的整数幂

  • 三格板是一种 L 形的物体，它能覆盖棋盘的三个格子

  • 步骤
    • 用(n2 - 1)/3个三重格放置在n×n的缺陷棋盘上，正好能够覆盖所有方格。
    • 划分为四个小棋盘。
    • 其中一个是4×4缺陷棋盘。
    • 在其它三个4×4棋盘都相邻的拐角上放一个三格板，使它们也成为缺陷棋盘。
    • 递归地覆盖四个4×4缺陷棋盘。

  • 复杂度分析

    \[T(K)=\left\{ \begin{aligned} O(1)　　　　if 　k = 1\\T(k - 1) + O(1)　if　k>1\end{aligned} \right.\]

5.2 大整数乘法

  • 原有的算法，诸位乘法，错位相加

    • 复杂度：O（n2）

  • 分治的算法

    • 将两个n位的乘数各分成相同长度的两部分

    • a b
      c d

    • XY = ac 2n + (ad+bc) 2n/2 + bd

    • 复杂度分析

      \[T(n)=\left\{ \begin{aligned} O(1)　　　　if 　n = 1\\4T(n / 2) + O(n)　if　n>1\end{aligned} \right.\]

      T(n) = O(n2)

  • 改进的分治算法
    • XY = ac 2n + ((a - b)(c - d) + ac + bd) 2n/2 + bd
    • XY = ac 2n + ((a + b)(c + d) - ac - bd) 2n/2 + bd
  • 复杂度分析
    • \[T(n)=\left\{ \begin{aligned} O(1)　　　　if 　n = 1\\3T(n / 2) + O(n)　if　n>1\end{aligned} \right.\]
    • T(n) = O(nlog3) = O(n1.59)

  • 问题细节

    • 两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。

5.3 Strassen 矩阵乘法

  • 传统方法：O(n3)
    • A和B的乘积矩阵C中的元素C[i,j]定义为:image-20200323171118037
    • 若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C[i] [j]，需要做 n 次乘法和n-1次加法。此，算出矩阵C的 个元素所需的计算时间为O(n3)
    • 复杂度分析：
      • \[T(n)=\left\{ \begin{aligned} O(1)　　　　if 　n = 2\\8T(n / 2) + O(n*n)　if　n>2\end{aligned} \right.\]

6.动态规划

6.1 最优二叉树搜索问题

  • 二叉查找树

    • 1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
    • 2）若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
    • 3）左、右子树也分别为二叉查找树。

    在随机的情况下，二叉查找树的平均查找长度为O(logn)。

  • 查找概率

    • 设{r1, r2, …, rn}是n个记录的集合，其查找概率分别是{p1, p2, …, pn}，最优二叉查找树是以这n个记录构成的二叉查找树中具有最少平均比较次数的二叉查找树，即

      image-20200325110945334

      最小，其中pi是记录ri的查找概率，ci是在二叉查找树中查找ri的比较次数。

  • 递推关系

    • 设T(i, j)是由记录{ri, …, rj}(1≤i≤j≤n)构成的二叉查找树，C(i, j) 是这棵二叉查找树的平均比较次数。虽然最后的结果是C(1, n)，但遵循动态规划法的求解方法，需要求出所有较小子问题 C(i, j) 的值。考虑从{ri, …, rj}中选择一个记录rk作为二叉查找树的根结点，可以得到如下关系：

      image-20200325111252258

    • 因此，得到如下动态规划函数：

      image-20200325111337367

    • 设一个二维表C[n+1] [n+1]，其中C[i][j]表示二叉查找树T(i, j)的平均比较次数。

    • 当k=1 时， 求C[i] [j] 需要用到C[i] [0] ， 当k=n 时， 求C[i] [j] 需要用到C[n+1] [j]，所以，二维表C[n+1] [n+1]行下标的范围为1～n+1，列下标的范围为0～n。

    • 为了在求出由{r1, r2, …, rn}构成的二叉查找树的平均比较次数的同时得到最优二叉查找树，设一个二维表R[n+1] [n+1]，其下标范围与二维表C相同，R[i][j]表示二叉查找树T(i, j)的根结点的序号。

      image-20200325113445445

  • 构造二维表

    • 例如，集合{A, B, C, D}的查找概率是{0.1, 0.2, 0.4, 0.3}，二维表C和R的初始情况如图所示。

      image-20200325111711630

    • 左图为相应节点的概率（平均比较次数），右图表示二叉查找树T(i, j)的根结点的序号

    • 求C[i][j]时，设以C[i] [i-1],C[j+1] [j],C[i] [j]三个点形成的直角三角形的次斜边上的值累加和为S(斜)，直角边上对应两点的和为S(直)，显然S[直]有j-i+1个，则C[i] [j]=S[斜]+min{S[直]}。下面举个例子求C[1] [3]的值，如图所示： image-20200325112323413

      S(斜)=0.1+0.2+0.4=0.7，S(直)=min{S1(直),S2(直),S3(直)}=min{0+0.8,0.1+0.4,0.4+0}=0.4，则C[1][3]=0.7+0.4=1.1。同理，求C[2][4]，如下图所示，C[2][4]=1.4。

    • 代码：

      void OptimalBST(double a[],double b[],int n,double **R,int **mink,double **C)
{
	//初始化
	for(int i=0; i<=n; i++)
	{
		C[i+1][i] = a[i];
		R[i+1][i] = 0;
	}
	for(int d=0; d<n; d++) 
		for(int i=1; i<=n-d; i++) //对角线逐条计算
		{ 
			C[i][j]=C[i][j-1]+a[j]+b[j];
			R[i][j]=R[i+1][j];
			mink[i][j]=i;
			for(int k=i+1; k<=j; k++)
				if(R[i][k-1]+R[k+1][j]<R[i][j])
				{
					R[i][j]= R[i][k-1]+R[k+1][j];
					mink[i][j]=k; 
				}
			R[i][j]+=C[i][j];
		}
}