算法概述

算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有下列5个重要特性：

• 有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
• 确定性：算法中的每一条指令必须有确切的含义，理解时不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
• 可行性：一个算法是可行的，即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
• 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
• 输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

常用的表示算法的方法有：

• 自然语言：优点是易理解；缺点是易出现二义性，算法通常很冗长。

• 流程图：优点是直观易懂；缺点是严密性不如程序设计语言，灵活性不如自然语言。

• 程序设计语言：优点是能用计算机直接执行；缺点是抽象性差，使算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，要求算法设计者掌握程序设计语言及编程技巧。

• 伪代码：伪代码是介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，同时结合自然语言来表达。

  计算机科学家从来没有对伪代码的书写形式达成过共识。

  在伪代码中，可以采用最具表达力的、最简明扼要的方法来表达一个给定的算法。

算法分析

复杂度

由于时间复杂度与空间复杂度分别对算法占用的时间和空间资源进行分析，计算方法相似。

算法的时间复杂度分析主要时分析算法的运行时间，即算法执行所需要的基本操作数。算法时间复杂度以算法中基本操附重复执行的次数（简称为频度）作为算法的时间度量。一般不必要精确计算出算法的时间复杂度，只要大致计算出相应的数量级即可。

算法的复杂度通常是用大O表示法。

• 加法规则：多项相加，保留最高阶项，并将系数化为1；
• 乘法规则：多项相乘都保留，并将系数化为1。

递归式的时间（空间）复杂度：

$$ 递归的次数 \times 每次递归的时间（空间）复杂度 $$

渐进符号

可以用渐进符号来表示渐进复杂度。

渐进符号包括：

• $O$：算法运行时间的渐进上界。

  给定一个函数$g(n)$，$O\big( g(n) \big) = \{ f(n):\exists 正常数c和n_0, 使得\forall n \ge n_0, 有 0 \le f(n) \le cg(n) \}$。

  即，当$n \ge n_0$时，$f(n) \le c \cdot g(n) $。

• $\Omega$：算法运行时间的渐进下界。

  给定一个函数$g(n) $，$O\big( g(n) \big) = \{ f(n):\exists 正常数c和n_0,使得\forall n \ge n_0, 有 0 \le cg(n) \le f(n) \}$。

  即，当$n \ge n_0$时，$c \cdot g(n) \le f(n)$。

• $\Theta$：算法运行时间的渐进上界和渐进下界，即渐进紧致界（又叫紧缺界）。

  给定一个函数$g(n)$，$O\big( g(n) \big) = \{ f(n):\exists 正常数c_1、c_2和n_0,使得\forall n \ge n_0, 有 0 \le c_1g(n) \le f(n) \le c_2g(n) \}$。

  即，当$n \ge n_0$时，$c_1g(n) \le f(n) \le c_2g(n)$。

算法设计方法

分治法

任何一个可以用计算机求解的问题所需要的计算时间都与其规模有关。要想直接解决一个较大的问题，有时是相当困难的。问题的规模越小，解题所需要的计算时间往往越少，从而较容易处理。分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较小的相同问题，以便各个击破，分而治之。

如果规模为$n$的问题可分解成$k$个子问题（$1 < k \le n $），这些子问题互相独立且与原问题相同。分治法产生的子问题往往是原问题的较小模式。

一般来说，分治算法在每一层递归上都有3个步骤：

1. 分解：将原问题分解成一系列子问题。

2. 求解：递归地求解各子问题。

   若子问题足够小，则直接求解。

3. 合并：将子问题的解合并成原问题的解。

分治的典型实例有：

• 归并排序；
• 快速排序；
• 最大子段和问题。

递归

递归是指子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方法。还有一些问题，虽然其本身并没有明显的递归结构，但用递归技术来求解使设计出的算法简洁易懂且易于分析。

递归有两个基本要素：

• 边界条件（递归出口）：确定递归到何时终止。
• 递归模式（递归体）：大问题是如何分解为小问题的。

递归可以将大规模的问题分解为若干个小规模的问题，然后先解决小规模问题，再将解决完的小规模问题合并再一起，再次进行处理，最后解决完所有问题。这与分治的思想不谋而合。

递归是分治的一个解决方案，而分治并不一定需要通过递归实现。分治还可以通过循环结构实现。

动态规划法

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合用动态规划法求解的问题，经分解得到的子问题往往不是独立的。不同子问题的数目常常只有多项式量级，可以用一个表来记录所有己解决的子问题的答案，在需要时再找出己求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值。而最优解可能会有多个，动态规划算法能找出其中的一个最优解。设计一个动态规划算法，通常按照以下几个步骤进行：

1. 找出最优解的性质，并刻画其结构特征。

2. 递归地定义最优解的值。

3. 以自底向上的方式计算出最优值。

   到此步骤为止的以上步骤（包括此步骤），是动态规划算法的基本步骤。

   如果需要给出最优解，通常需要在此步骤中记录更多的信息，以便在步骤4中根据所记录的信息快速构造出一个最优解。

4. 根据计算最优值时得到的信息，构造一个最优解。

   在只需要求出最优值的情形下，该步骤可省略；若需要求出问题的一个最优解，该步骤必须执行。

对于一个给定的问题，若其具有以下两个性质，可以考虑用动态规划法来求解：

• 最优子结构：如果一个问题的最优解中包含了其子问题的最优解，就说该问题具有最优子结构。

  当一个问题具有最优子结构时，提示我们动态规划法可能会适用，但是此时贪心策略可能也是适用的。

• 重叠子问题：指用来解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。

  即当一个递归算法不断地调用同一个问题时，就说该问题包含重叠子问题。

  此时若用分治法递归求解，则每次遇到子问题都会视为新问题，会极大地降低算法的效率，而动态规划法总是充分利用重叠子问题，对每个子问题仅计算一次，把解保存在一个在需要时就可以查看的表中，而每次查表的时间为常数。

动态规划的经典问题：

矩阵连乘：

两个矩阵$A_{(m \cdot n)}$和$B_{(n \cdot p)}$相乘的次数为：$m \cdot n \cdot p$，相乘后得到的新矩阵为：$(A \cdot B)_{(m \cdot p)}$。

贪心法

和动态规划一样，贪心法也经常用于解决最优化问题。

与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前己有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换而言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不能保证总能获得全局最优解，但通常能得到较好的近似最优解。

例如，平时购物找钱时，为使找回的零钱的硬币数最少，从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种，这就是在采用贪心法。这种方法在这里总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如果只有面值分别为1、5和11单位的硬币，而希望找回总额为15单位的硬币，按贪心算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的解答应是3个5单位面值的硬币。

贪心法的典型实例：

• 活动选择问题
• 背包问题

回溯法

回溯法有“通用的解题法”之称，用它可以系统地搜索一个问题的所有解或任一解。

回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解：

• 如果肯定不包含：跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯；
• 否则：进入该子树，继续按深度优先的策略进行搜索。

使用回溯法求解问题：

• 用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束；
• 用来求问题的任一解时，只要搜索到问题的一个解就可以结束。

回溯法适用于解一些组合数较大的问题。

回溯法经典实例：

• 0-1 背包问题
• n 皇后问题

解空间

应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。

通常将解空间表示为树或图的形式。

基本思想

确定解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。

1. 开始时根结点成为一个活结点（有多个活结点），同时也成为当前的扩展结点（只能有一个扩展结点）。
2. 在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。
3. 如果在当前扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。
4. 回溯法即以这种工作方式递归地在解空间中搜索，直到找到所要求的解或解空间中己无活结点时为止。

运用回溯法解题通常包含以下3个步骤：

1. 针对所给问题，定义问题的解空间。
2. 确定易于搜索的解空间结构。
3. 以深度优先的方式搜索解空间。

限界函数

限界函数的设计是回溯法的核心问题，也是难题。问题的解空间往往很大，为了有效地进行搜索，需要在搜索的过程中对某些结点进行剪枝，而对哪些结点进行剪枝，需要设计限界函数来判断。

设计限界函数的通用的指导原则是尽可能多和尽可能早地“杀掉”不可能产生最优解的活结点。好的限界函数可以大大减少问题的搜索空间，从而大大提高算法的效率。

分支限界法

分支限界法类似于回溯法，也是一种在问题的解空间树$T$上搜索问题解的算法。在一般情况下，分支限界法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

分支限界法以广度优先或以最小耗费优先的方式搜索解空间树$T$。

分支限界法的搜索策略是：每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有子结点。在这些子结点中，那些导致不可行解或非最优解的子结点被舍弃，其余子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

目前己有许多利用分支限界法解决大量离散最优化的实际问题的实例。

与回溯法相似，限界函数的设计是分支限界法的一个核心问题和难题。如何设计限界函数来有效地减小搜索空间是应用分支限界法要考虑的问题。

根据从活结点表中选择下一扩展结点的不同方式，可将分支限界法分为几种不同的类型。最常用的有以下两种：

• 队列式（FIFO，先进先出）分支限界法：将活结点表组织成一个队列，并按队列的先进先出原则选择下一个结点作为扩展结点。

• 优先队列式分支限界法：将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点作为扩展结点。

  结点优先级：通常用一个与该结点相关的数值$p$来表示，规定$p$值较大的结点优先级较高。

  在算法实现时，有两种实现方式：

  • 通常用一个最大堆（根结点比左右子结点大）来实现最大优先队列，用最大堆的Deletemax操作（删除最大堆顶）抽取堆中下一个结点成为当前扩展结点。
  • 最小优先队列规定$p$值较小的结点优先级较高。通常用一个最小堆根结点比左右子结点小）来实现最小优先队列，用最小堆的Deletemin操作（删除最小堆顶）抽取堆中下一个结点成为当前扩展结点。

分支限界法经典实例：0-1 背包问题。

总结

算法实例

最大子段和问题

给定$n$个整数$a_1, a_2, \cdots, a_n$（可能有负数），求该序列形如$\sum\limits_{k=i}^{j} a_k$的子段和的最大值。当序列中所有整数均为负数时，其最大子段和为$0$。即所求最大值为：

$$ max \left\{ 0, \mathop{max}\limits_{1 \le i \le j \le n} \sum_{k=i}^{j} a_k \right\} $$

给定序列$A[1 \dots n]$，采用分治策略解决问题：

1. 分解：将$A[1 \dots n]$分解为长度大致相等的两段$A\left[1 \dots {n}/{2}\right]$和$A\left[ {n}/{2}+1 \dots n \right]$，分别求出这两段的最大子段和。

   最大字段和有3中情形：

   1. $A[1 \dots n]$与$A\left[1 \dots {n}/{2}\right]$（左边那段）的最大子段和相同。
   2. $A[1 \dots n]$与$A\left[ {n}/{2}+1 \dots n \right]$（右边那段）的最大子段和相同。
   3. $A[1 \dots n]$的最大子段和为$\sum\limits_{k=i}^{j} a_k$，且$1 \le i \le n/2$，$n/2+1 \le j \le n$（横跨两个子段）。

2. 解决：

   • 情形1和2：再将子段进行分解，按照以上3种情形递归地计算子段的最大子段和。

   • 情形3：$A\left[1 \dots {n}/{2} \right]$和$A\left[ {n}/{2}+1 \dots n \right]$都包含了最优子段的一部分。

   • 在$A\left[1 \dots {n}/{2}\right]$中计算出：

     $$ s_1 = \mathop{max}\limits_{1 \le i \le \frac{n}{2}} \left(\sum_{k=i}^{\frac{n}{2}} A[ \ k \ ]\right) $$

   • 在$A\left[ {n}/{2}+1 \dots n \right]$中计算出：

     $$ s_2 = \mathop{max}\limits_{ \frac{n}{2}+1 \le j \le n } \left(\sum\limits_{k=\frac{n}{2}+1}^{j} A[ \ k \ ]\right) $$

   $s_1 + s_2$即为情形3的最优值。

3. 合并：取分解阶段3种情况下最大子段和中最大值为原问题的解。

以上3个步骤需要递归地进行，实际情况是：

1. 将$A[1 \dots n]$分解为由单个元素组成的$n$个子序列$\{ [a_1], [a_2], \cdots, [a_n] \}$，这$n$个子序列的最大子段和即为其唯一一个元素的值。

2. 自底向上，先分别将相邻的两个子段组合起来，并根据上述分解中描述的3种情形计算其组合后的最大子段和。

   例如$[a_1, a_2]$最大子段和有3种可能：

   1. 情形1：$[a_1]$；
   2. 情形2：$[a_2]$；
   3. 情形3：$[a_1, a_2]$（即将$a_1$作为$s_1$，$a_2$作为$s_2$）。

   将取$\{[a_2], [a_1, a_2]\}$中值最大的序列作为$s_1$返回给上层调用。

   $[a_3, a_4]$最大子段和也是类似以上情况，最后取$\{[a_3], [a_3, a_4]\}$中值最大的序列作为$s_2$返回给上层调用。

   $A[1 \dots n]$中其他序列也是类似的操作。

3. 接着来到上一步骤的上层调用中。

   例如$[a_1, a_2, a_3, a_4]$的最大子段和也是有3种可能：

   1. 情形1：$[a_1, a_2]$；
   2. 情形2：$[a_3, a_4]$；
   3. 情形3：$[a_1, a_2]$的$s_1$加上$[a_3, a_4]$的$s_2$。

   最后计算$[a_1, a_2, a_3, a_4]$的$s_1$值，可能为$[a_1, a_2, a_3, a_4]$、$[a_2, a_3, a_4]$、$[a_3, a_4]$或$[a_4]$，取其中值最大者。

4. 其他层次的调用也是类似上述步骤，最后得到$[a_1, a_2, \cdots, a_{\frac{n}{2}}]$和$[a_{\frac{n}{2}+1}, \cdots, a_n]$的$s_1$和$s_2$还有它们的两个最大子段和。 根据3种情况，取3种情况中最大值者作为$A[1 \dots n]$的最大子段和。

0-1 背包问题

有$n$个物品，第$i$个物品价值为$v_i$，重量为$w_i$，背包可容纳最大重量为$W$，$v_i$、$w_i$和$W$均为非负数。考虑如何选择装入背包的物品，使装入背包的物品总价值最大。该问题可以形式化描述如下：

• 目标函数：$max\sum\limit_{i=1}^{n}v_ix_i$；

• 约束条件：$\sum\limit_{i=1}^{n}w_ix_i \le W$，$x_i \in {0, 1}$。

  当物品$i$放入背包时，$x_i$为$1$，否则为$0$。

满足约束条件的任一集合（$x_1, x_2, \cdots, x_n$）是问题的一个可行解，问题的目标是求问题的一个最优解。

使用动态规划求解

根据动态规划的4个步骤求解该问题：

1. 刻画 0-1 背包问题的最优解的结构：

   有两种情况：

   • $x_n = 1$：即问题的最优解包含了物品$n$，那么其余$x_1, x_2, \cdots, x_{n-1}$一定构成子问题：物品$1, 2, \cdots, n-1$在容量为$W-w_n$时的最优解。
   • $x_n = 0$：即最优解不包含物品$n$，那么其余$x_1, x_2, \cdots, x_{n-1}$一定构成子问题：物品$1, 2, \cdots, n-1$在容量为$W$时的最优解。

2. 递归定义最优解的值：

   设$c[i, w]$，表示背包可容纳重量为$w$时，第$i$个物品导致的最优解的总价值：

   $$ c[i, w] = \begin{aligned} 0, & i = 0 或 w = 0 \\ c[i-1, w], & w_i > w \\ max\{ c[i-1, w-w_i] + c[i-1, w] \}, & i > 0 且 w_i \le w \end{aligned} $$

3. 计算背包问题最优解的值。

4. 根据计算的结果构造问题最优解。

使用回溯法求解

以$n=3, W=30$的0-1背包问题为例，物品的价值和重量如下：

1. 定义问题的解空间：

   

   其中$X(i)$即为$x_i$。

2. 定义限界函数：

   考虑贪心策略，先对所有物品按其单位重量价值从大到小排序。对搜索空间树中的某个结点，有确定的$X(i)$（$1 \le i \le k$），而其他的$X(i)$（$k + 1 \le i \le n$）待定。

   此时可以将0-1背包问题松弛为背包问题，求从当前结点扩展下去，计算能获得的最大价值。若该价值比当前已经得到的某个可行解的值要小，则该结点不必再扩展。

3. 以深度优先的方式搜索解空间：

   1. 开始时根结点是唯一的活结点，也是当前的扩展结点。在扩展结点处，按照深度优先策略移至结点$B$或$C$。

      假设先移至$B$，此时$A$和$B$均是活结点，结点$B$成为当前扩展结点。

      当前$X(1) = 1$表示选择了物品$1$，当前背包剩余容量$w = 14$，获取的价值是$v=45$。

   2. 从当前扩展结点$B$可以移至$D$或$E$。

      由于$w_2=15$，移至$D$不是一个可行解，所以选择移至$E$。

      此时$E$成为新扩展结点，$A$、$B$和$E$是当前的活结点，当前的$w$和$v$不变。

   3. 从$E$可以移至$J$或$K$。

      移至$J$导致一个不可行解，所以移至$K$，$K$成为新扩展结点。

      $K$是叶结点，故得到一个可行解。解$x$的取值是由根到叶结点$K$的路径唯一确定的，即$x = (1, 0, 0)$，对应$v = 45$。

      由于$K$已不能在向纵深扩展，所以$K$成为死结点。返回到上一个活结点$E$，此时$E$也没有可扩展的结点，它也成为一个死结点。$B$此时也是死结点，最后回到$A$。

   4. $A$还可扩展，按照类似上述步骤继续搜索。搜索结束后找到的最好解就是0-1背包问题的最优解。

背包问题

有$n$个物品，第$i$个物品价值为$v_i$，重量为$w_i$，背包容量为$W$，$v_i$、$w_i$和$W$均为非负数。背包问题与0-1背包问题类似，但是每个物品可以部分装入背包，即$0 \le x_i \le 1$。

假设$n = 5, W = 100$，各物品的重量、价值和单位重量的价值如图：

为了得到最优解，必须把背包放满。用贪心法求解，有3种方式：

• 按最大价值优先放入背包的原则：

  1. 先放物品$1$和$4$，获得价值$65+60=125$，背包容量剩$100-30-50=20$。
  2. 此时物品$5$价值最大，但不能全部放入背包。而将物品$2$和$3$放入背包比把物品$5$的一半放入背包的价值大。
  3. 把物品$2$放入背包，目前获得价值共$125+20=145$，剩余容量$20-10=10$。
  4. 此时可再放入物品$3$的$\cfrac{1}{3}$，得到总价值$145 + 1.5 \times 10 = 160$。

  对应的解为$\left\{1,\ 1,\ \cfrac{1}{3},\ 1,\ 0 \right\}$。

• 按最小重量优先放入背包的原则：将物品$2$、$3$、$1$和$5$放入背包，刚好装满，得到价值$20+30+60+40=155$，对应的解为$\{ 1, 1, 1, 0, 1 \}$。

• 按最大单位重量价值优先放入背包的原则：

  1. 将物品$1$、$2$和$3$放入背包，得到价值$65+20+30=115$，剩余容量$100-30-10-20=40$。
  2. 还可将物品$4$的$\cfrac{4}{5}$放入背包，得到总价值$115 + \cfrac{4}{5} \times 60 = 163$。

  对应的解为$\left\{ 1,\ 1,\ 1,\ \cfrac{4}{5},\ 0 \right\}$

最长公共子序列（LCS）

非形式化地讲，子序列可以是从给定序列中随意地（不一定是连续的）去掉若干元素（可能一个也不去掉）后所形成的序列。令序列$X = x_1x_2\cdots x_m$，序列$Y=y_1y_2\cdots y_k$是$X$的子序列，存在$X$的一个严格递增下标序列$<i_1, i_2, \cdots, i_k>，使得对于所有的$j=1, 2, \cdots, k$有$x_{i_j}=y_j$。

公共子序列：给定两个序列$X$和$Y$，序列$Z$同时是$X$和$Y$的子序列，这个序列$Z$即为$X$和$Y$的公共子序列。

最长公共子序列问题定义为：给定序列$X=x_1x2 \cdots x_m$和序列$Y=y_1y2 \cdots y_n$，求这两个序列的最长公共子序列。

动态规划法求解最长公共子序列问题：

1. 刻画最长公共子序列问题的最优子结构：

   LCS最优子结构定理：

   • $x_m = y_n$：$z_k = x_m = y_n$，且$Z_{k-1}$是$X_{m-1}$和$Y_{n-1}$的一个最长公共子序列。
   • $x_m \neq y_n$：
     • $z_k \neq x_m$：蕴含$Z$是$X_{m-1}$和$Y$的一个最长公共子序列；
     • $z_k \neq y_n$：蕴含$Z$是$X$和$Y_{n-1}$的一个最长公共子序列。

2. 递归定义最优解的值：

   设$l[i, j]$表示序列$X_i$和$Y_j$的最长公共子序列的长度：

   $$ l[i, j] = \begin{aligned} 0, & i=0 或 j=0 \\ l[i-1, j-1], & i,j > 0 且 x_i = y_j \\ max(l[i-1, j], l[i, j-1]), & i,j > 0 且 x_i \neq y_j \end{aligned} $$

3. 计算最优解的值：

   根据上述递归式自底向上地求出最优解的值。将$l[i, j]$的值存储在表$l[1 \dots m, 1 \dots n]$中，以行为主序从左到右计算表$l$中的元素，同时维持表$b[1 \dots m, 1 \dots n]$，用其中的元素$b[i, j]$记录使得$l[i, j]$取最优值的最优子结构。

   例如$X=ABCBDAD$和$Y=BDCABA$，对应的表$l$和$b$如图：

   

4. 构造最优解：

   用表$b$中的信息构造$X$和$Y$的一个LCS。从$b[m, n]$开始，在表中沿着箭头方向跟踪，$b[i, j]$的值和含义如下：

   • $“\nwarrow”$：表示$x_i = y_j$为LCS中的元素，接下来要判断（跟踪）$b[i-1, j-1]$。
   • $“\uparrow”$：表示$x_i \neq y_j$，此时需要判断（跟踪）$b[i-1, j]$。
   • $“\leftarrow”$：表示$x_i \neq y_j$，此时需要判断（跟踪）$b[i, j-1]$。

活动选择问题

活动选择问题是指若干个具有竞争性的活动，要求互斥使用某一公共资源时，如何选择最大的相容活动集合。

假设有一个需要使用某一资源的$n$个活动组成的集合$S=\{a_1, a_2, \cdots, a_n\}$，该资源一次只能被一个资源占用。

• 活动$a_i$有一个开始时间$s_i$和结束时间$f_i$，且$0 \le s_i \le f_i < \infin$。
• 一旦被选择后，活动$a_i$就占据半开时间区间$[s_i, f_i)$。
• 如果两个活动$a_i$和$a_j$的时间区间互不重叠，则称活动$a_i$和$a_j$是兼容的。

活动选择问题就是要选择出一个由互相兼容的活动组成的最大子集合。

该问题可用动态规划法和贪心法求解。

使用贪心法求解：

定义集合$S_{ij} = \{a_k \in S: f_i \le s_k < f_k \le s_j \}$。为了完整表示，加入两个虚拟活动$a_0$和$a_{n+1}$，其中$f_0=0,s_{n+1} = \infin$，则$S = S_{0, n+1}$。

定理：

对于任意非空子问题$S_{ij}$，设$a_m$是$S_{ij}$中具有最早结束时间的活动，那么有两种情况：

• $a_m$在$S_{ij}$的某个最大兼容活动子集中。
• 子问题$S_{im}$为空，选择$a_m$将使$S_{mj}$为唯一可能非空的子问题。

n 皇后问题

$n$皇后问题要求在$n \times n$格的棋盘上放置$n$个皇后，使得它们彼此不受攻击。按照规则，皇后可以攻击与之处在同一行、同一列或同一斜线上的其他任何棋子。$n$皇后问题等价于要求在一个$n \times n$棋盘上放置$n$个皇后，使得任何两个皇后不能被放在同一行、同一列或同一斜线上。

求解过程从空棋盘开始，设在第$1$行至第$m$行都己经正确地放置了$m$个皇后：

1. 在第$m+1$行上，从第1$列开始找适合放置皇后的位置，共有$n$个可选位置。当一个位置不合适时就顺序选择下一列的位置进行判断。

   一个位置上共有以下几种情形：

   • 当前位置的所在列上，已经有一个皇后存在，该位置不合适。
   • 当前位置所在的斜线上，已经有一个皇后存在，该位置不合适。
   • 当前位置所在的列和斜线上，均无皇后存在，该位置合适。

2. 接着往下一行，寻找下一行中适合放皇后的位置，然后再继续往下找。

   此时有以下几种情形：

   • 一直寻找到第$n$行，每一行上都有适合放皇后的位置。此时为一个可行解。

     如果第$n$行还有剩余的位置，那么便继续判断这些位置，以希望再获得一个可行解；否则进行回溯，按步骤1的方式改变上一行的位置。

   • 往下搜寻，在中途发现某一行上的所有位置都不能放置皇后，此时也要进行回溯，回到上一行按步骤1的方式改变位置。

用回溯法求解4-皇后问题：

查找算法

查找是一种常用的基本运算。查找表是指由同一类型的数据元素（或记录）构成的集合。

查找表经常要进行的操作：

• 查询某个特定的数据元素是否在查找表中。
• 检索某个特定的数据元素的各种属性。

通常将只进行这两种操作的查找表称为静态查找表。

查找表经常要进行的另外两种操作：

• 在查找表中插入一个数据元素。
• 从查找表中删除一个数据元素。

需要在查找表中插入或删除元素，称此类查找表为动态查找表。

关键字是数据元素（或记录）的某个数据项的值，用它来识别（标识）这个数据元素。

• 主关键字：能唯一标识一个数据元素的关键字。
• 次关键字：能标识多个数据元素的关键字。

平均查找长度

查找算法基本操作是“将记录的关键字与给定值进行比较”。因此，通常以“其关键字和给定值进行过比较的记录个数的期望值”作为衡量查找算法好坏的依据。

查找算法在查找成功时的平均查找长度关键字和给定值比较次数的期望值：

$$ ASL = \sum_{i=1}^{n}{P_iC_i} $$

• $P_i$为对表中第$i$个记录进行查找的概率，

  一般认为$P_i=\cfrac{1}{n}, 1 \le i \le n$，即$\sum_{i=1}^{n}{P_i}$；

• $C_i$为查找成功时，已经进行过比较的关键字个数。

查找算法

静态查找表有以下查找方法：

• 顺序查找；
• 折半查找；
• 分块查找。

动态查找表有以下查找方法：

• 二叉排序树；
• 平衡排序树；
• B-树；
• 哈希表。

顺序查找

顺序查找是从表的一端开始，按照顺序（从左往右或从右往左）逐一进行查找。顺序查找的方法对于顺序存储方式和链式存储方式的查找表都适用。

顺序查找中，$C_i$取决于所查记录在表中的位置。一般情况下，$C_i = n - i + 1$，在等概率下，顺序查找的平均查找长度为：

$$ ASL_{ss} = \cfrac{1}{n} \sum_{i=1}^{n}{(n-i+1)} = \cfrac{n+1}{2} $$

二分查找

二分查找又叫折半查找，是在有序列表的基础上进行查找，每次查找可以筛掉一半的元素。步骤如下：

以升序数列$L[0…n-1]$为例，假设要查找的数为$x$：

让$x$与数列中间位置的元素$L\left[ \left\lfloor \cfrac{n}{2} \right\rfloor \right]$进行比较，如果相等则返回该元素下标，否则：

• 如果$x$比中间元素小，递归地对中间元素左边的数列（比$x$小的元素）进行二分查找；
• 如果$x$比中间元素大，递归地对中间元素右边的数列（比$x$大的元素）进行二分查找。

折半查找的过程可用二叉树描述。$n$个结点的二叉树深度为$\lfloor log_2{n} \rfloor + 1$，折半查找进行比较的关键字个数最多不超过树的深度。所以，折半查找在查找成功时和给定值进行比较的关键字个数最多为$\lfloor log_2{n} \rfloor + 1$。

折半查找的平均查找长度（假设结点总数为$n=2^h-1$，即折半查找树为深度$h=log_2(n+1)$的满二叉树）：

$$ ASL_{bs} = \cfrac{1}{n} \sum_{i=1}^{n}{i \times 2^{i-1}} = \cfrac{n+1}{n} log_2{(n+1)} - 1 $$

当$n$值较大时，$ASL_{bs} \approx log_2{(n+1)} - 1$。

哈希表

哈希表查找（又叫散列表查找）是通过散列技术，将存储位置和关键字构建一个确定的关系$H$，使得每个关键字$key$对应一个存储位置$H(key)$。其中，$H$称为哈希函数或者散列函数。

根据设定的哈希函数$H(key)$和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这块连续的空间称为哈希表或散列表，这一映射过程称为哈希造表或散列表，所得的存储位置称为哈希地址或散列地址。

对于哈希表，主要考虑两个问题：

• 如何构造哈希函数；
• 如何解决冲突。

冲突

对于某个哈希函数$H$和两个关键字$key_1$和$key_2$,如果$key_1 \neq key_2$，而$H(key_1)=H(key_2)$，则称为冲突。

具有相同哈希函数值的关键字对该哈希函数来说称为同义词。

一般情况下，冲突只能尽可能减少而不能完全避免。

哈希函数的构造方法

常用的哈希函数构造方法有：

• 直接定址法；

• 数字分析法；

• 平方取中法；

• 折叠法；

• 随机数法；

• 除留余数法

  ……

哈希函数的构造要考虑到：

• 压缩性：节省存储空间；

• 散列性：尽量减少冲突。

  要减少冲突，就要设法使哈希函数尽可能均匀地把关键字映射到存储区的各个存储单元。在构造哈希函数时，一般都要对关键字进行计算，且尽可能使关键字的所有组成部分都能起作用。

除留取余数法

除留取余数法是最常用的构造散列函数方法。

除留取余数法：

$$ f(key)=key \enspace mod \enspace p\quad (p\le m),\ m为散列表长 $$

$mod$ 是取模运算。

根据经验，若散列表表长为$m$，通常$p$为小于或等于表长（最好接近$m$）的最小质数，可以更好的减小冲突。

冲突处理方法

解决冲突就是为出现冲突的关键字找到另一个“空”的哈希地址。在处理冲突的过程中可能得到一个地址序列$H_i,(i=1,2,\dots,k)$。常见的处理冲突的方法有以下几种：

• 开放地址法；
• 多重散列法（再哈希法）；
• 链地址法；
• 公共溢出区法……

开放地址法

开放地址就是一旦发生冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并且记录它。

有三种寻找空散列地址的方法：

• 线性探测法（线性探测再散列）：

  $$ H_i=(H(key)+d) mod m $$

  其中：

  • $d$取$0,1,2,…,m-1$；
  • $m$为散列表的长度。

  $d$初始为0，如果有冲突，那么$d$就通过递增来寻找空的散列地址。

• 二次探测法（二次探测再散列）：

  $$ H_i=(H(key)+q^2) mod m $$

  其中：

  • $q$取$0,1,-1,2,-2,…,\pm k$，$k \le \cfrac{m}{2}$
  • $m$为散列表的长度

  二次探测法其实是对线性探测的一个优化，增加了平方可以不让关键字聚集在某一块区域。

线性探测法市能使第$i$个哈希地址的同义词存入第$i+1$个哈希地址，这样本应存入第$i+1$个哈希地址的元素变成了第$i+2$个哈希地址元素的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“聚集”起来的现象，大大降低了查找效率。

排序算法

排序算法有稳定排序和不稳定排序两种。假设待排序序列中，$R_i$和$R_j$值相同，且$R_i$领先于$R_j$，排序后：

• 稳定排序：排序后$R_i$和$R_j$相对次序不变，$R_i$任领先于$R_j$；
• 不稳定排序：排序后可能出现$R_j$领先于$R_i$的情况。

根据记录存储的位置可分为：

• 内部排序：待排序记录存储在内存中进行排序的过程。
• 外部排序：排序记录的数量很大，内存无法容纳全部记录，在排序过程需要对外存进行访问的排序过程。

排序过程需要进行的两种基本操作：

1. 比较两个关键字的大小。

   这种操作对于大多数排序方法来说是必需的。

2. 将记录从一个位置移动到另一个位置。

   这种操作可以通过改变记录的存储方式来避免。

排序算法及其时间、空间复杂度：

是否归位：在排序过程中，能否确定某些元素的最终排序位置。

选择排序

选择排序（Selection Sort）是一种简单直观的排序算法，无论什么数据进去都是 $O(n²)$ 的时间复杂度。

算法步骤：

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复步骤2，直到所有元素均排序完毕。

归位：在排序过程中，能确定某些元素的最终排序位置。

#include <stdio.h>

void selectionSort(int arr[], int len)
{
    for (int i = 0 ; i < len - 1 ; i++)
    {
        int min = i;
        for (int j = i + 1; j < len; j++)     // 走访未排序的元素
            // 找到最小值
            if (arr[j] < arr[min])
                min = j;
        // i 不是最小数时，将 i 和最小数进行交换
        if (i != min)
        {
            int tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp; 
        }
    }
}

int main(void)
{
    int arr[] = { 
        22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
    int len = (int)sizeof(arr) / sizeof(*arr);
    selectionSort(arr, len);
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}

冒泡排序

冒泡排序（Bubble Sort）是一种简单直观的排序算法。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法步骤：

假设一个序列长度为n，m（m≤n）是已排序完成的在末尾的数。

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。对比结束后，最后的元素会是最大的数。

3. 对接下来n-m个未排序的数重复步骤1和2，直到没有任何一对数字需要比较。

   第一趟对序列中所有n个数进行比对，第二趟对序列中n-1个未排序完成的数进行比对，以此类推。每次比对的数为n-m。

归位：在排序过程中，能确定某些元素的最终排序位置。

#include <stdio.h>

void bubbleSort(int arr[], int len)
{
    for (int i = 0; i < len - 1; i++)
        for (int j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1])
            {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
}

int main(void)
{
    int arr[] = { 
        22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
    int len = (int)sizeof(arr) / sizeof(*arr);
    bubbleSort(arr, len);
    for (int i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}

直接插入排序

直接插入排序的做法是：在插入第$i$个记录（$R_i$）时，序列中的前$i-1$个记录$R_1,R_2,\cdots,R_{i-1}$已排好序。将$R_i$与前面的有序序列做比较，找到应该插入的位置将$R_i$插入，并将插入位置后的记录依序向后移动。

如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

对于基本有序的序列用直接插入排序效率是最高的。

不归位：在排序过程中，不能确定某些元素的最终排序位置。

希尔排序

希尔排序又称为“缩小增量排序”，它是对直接插入排序方法的改进。

希尔排序的基本思想是：先将整个待排记录序列分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。

步骤如下：

1. 选择一个增量序列$t_1,t_2,…,t_k$，其中$t_i < t_{i-1}(1 \le i \le k),t_k = 1$；

   一般来说，$t_1 \le \cfrac{n}{2}$。

2. 按增量序列个数$k$，对序列进行$k$趟排序；

3. 每趟排序，根据对应的增量$t_i$，将待排序列分割成若干长度为$t_i$的子序列，分别对各子表进行直接插入排序。仅增量因子为$1$时，整个序列作为一个表来处理，表长度即为整个序列的长度。

归位：在排序过程中，能确定某些元素的最终排序位置。

计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是$Θ(n + k)$。计数排序不是比较排序，排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

计数排序是用来排序0到100之间的数字的最好的算法。

算法步骤：

1. 找出待排序的数组中最大和最小的元素。
2. 统计数组中每个值为 i的元素出现的次数，存入数组 C的第 i项。
3. 对所有的计数累加（从 C中的第一个元素开始，每一项和前一项相加）。
4. 反向填充目标数组：将每个元素 i放在新数组的第 C(i) 项，每放一个元素就将 C(i) 减去 1。

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

堆积是一种近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

算法步骤

1. 将待排序的数组构造出一个堆 H[0……n-1]；

2. 把堆首（堆顶结点，即最大值）和堆尾（堆的最下层最右边的结点）互换；

   此时不再对原堆顶（最大值）进行操作，即原堆顶已经被“移出”，堆的长度缩小1。

3. 把新的数组顶端数据调整到相应位置；

4. 重复步骤 2 到 3，直到堆的尺寸为 1。

归位：在排序过程中，能确定某些元素的最终排序位置。

快速排序

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

算法步骤

1. 从序列中选择一个元素作为“基准”（pivot）。
2. 将所有比基准数小的放在基准左边，所有比基准数大的放在基准右边（相同的数可以在任一边）。这个称为分区（partition）操作。
3. 分区完成后，该基准就会归到序列中的相应位置，该位置是排序完成后的位置。
4. 分别递归地把小于基准数的子序列（左边）和大于基准数的子序列（右边）重复执行1到3操作。

归位：在排序过程中，能确定某些元素的最终排序位置。

归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

1. 自上而下的递归；
2. 自下而上的迭代。

算法步骤：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4. 重复步骤 3 直到某一指针达到序列尾；将另一序列剩下的所有元素直接复制到合并序列尾。

不归位：在排序过程中，不能确定某些元素的最终排序位置。