Algorithm Exam Review

算法评估
- 复杂性概念
- 用特征方程解递归方程的通解
分治法
动态规划
贪心法
回溯法

算法评估

复杂性概念

时间复杂性与空间复杂性。

5 种渐进复杂性

渐进上界 $f(n) = O(g(n)) \approx a \leq b$
渐进下界 $f(n) = \Omega(g(n)) \approx a \geq b$
紧渐进界 $f(n) = \Theta(g(n)) \approx a = b$
非紧上界 $f(n) = o(g(n)) \approx a < b$
非紧下界 $f(n) = \omega(g(n)) \approx a > b$

题型：证明 $f(n)$ = *(g(n))

存在正常数 $c$ 和自然数 $n_0$ ，使得对所有 $n \geq n_0$ 有…

例题：证明关系

3n^2+4n^3=O(n^3)

解：

当 $n \geq 1$ 时，令 $f(n) = 3n^2 + 4n^3 \leq 3n^3 + 4n^3 = 7n^3$ 。所以存在 $c=7$ 和 $n_0 = 1$ 满足对于任意 $n \geq n_0$ ， $f(n) \leq cn^3$ ，即可证此题。

用特征方程解递归方程的通解

例题：求解线性递归关系

\begin{cases} x_{n+1} = 3x_n + 10x_{n-1}, \; n\geq 1 \\ x_0=2, \; x_1=3 \end{cases}

解：

用 $t^n$ 取代 $x_n$ ，有 $t^{n+1} = 3t^n + 10t^{n-1}$ ，两边分别除以 $t^{n-1}$ 得特征方程：

t^2 = 3t + 10

特征方程有两个不同的根

\begin{cases} t_0 = -2 \\ t_1 = 5 \end{cases}

则递归方程的通解为

x_n = c_1(-2)^n + c_25^n

由 $x_0 = 2$ 和 $x_1 = 3$ 得

\begin{cases} c_1 = 1 \\ c_2 = 1 \end{cases}

分治法

二分查找

略

快速排序

quick sort 在最坏情况下，快速排序会退化为冒泡排序，解决方式：内省排序 intro sort

归并排序

merge sort

线性时间排序

循环赛问题

拆分：偶数个对半分，奇数个先加一个成为偶数，再将加的去掉。
合并：左上角和右下角一组，右上角和左下角一组，划分后是奇数和偶数的处理方式不完全一样。

动态规划

基本要素

最优子结构（动态规划是对的）：原问题的最优解包含了其子问题的最优解，即原问题可以由子问题的最优解组合而成。
重叠子问题（动态规划会更快）：拆分出的子问题不总是新问题，朴素地求解会导致某些子问题被反复计算多次。

可以通过某种数据结构存储这些被重复计算的子问题的结果而避免重复计算。

矩阵连乘

对于一个序列 [A-Z]*AB 而言，不管 B 左边的子序列按怎样的顺序计算，其结果的形状一定是固定的，这就是这个问题的最优子结构。

最长公共子序列*

构造数组 c[][]，c[i][j] 存储序列 X[i] 和 Y[j] 的最长公共子序列长度。

void LCSLength(int m, int n, char* x, char* y, int** c) {
  for (int i = 1; i <= m; i++) c[i][0] = 0;
  for (int i = 1; i <= n; i++) c[0][i] = 0;
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      c[i][j] = x[i] == y[i]
        ? c[i-1][j-1] + 1
        : max(c[i-1][j], c[i][j-1]);
}

其中 c 数组中值是其左上角值 + 1 的点组合而成的序列就是最长公共子序列，结果可能不唯一。

最大子段和*

构造数组 b[]，b[i] 存储序列以下标 i 结尾的最大子段和。则有 b[j] = max(b[j-1] + a[j], a[j]), 1 <= j <= n。进一步发现，计算 b[j] 时只需要知道 b[j-1] 的值，因此不需要数组，只需要一个变量 b。

int maxSum(int n, int* a) {
  int sum = 0, b = 0;
  for (int i = 1; i <= n; i++) {
    b = b > 0 ? a[i] + b : a[i];
    sum = max(sum, b);
  }
  return sum;
}

0/1 背包

构造数组 dp[i][j]，i 是物品 id，j 是背包重量， dp[i][j] 的含义是从下标为 [0-i] 的物品里任意取，放进容量为 j 的背包，价值总和最大值。

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

参考这个文章

贪心法

特殊的最优子结构性质，全局最优解能通过对多个局部最优解中取最优得到。

活动安排*

设有n个活动的集合 E={1,2,…,n}，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间 si和一个结束时间 fi，且 si < fi。如果选择了活动i，则它在半开时间区间 [si, fi) 内占用资源。若区间 [si, fi) 与区间 [sj, fj) 不相交,则称活动i与活动j是相容的。也就是说，当 si≥fj 或 sj≥fi 时，活动 i 与活动 j 相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

将活动按照结束时间进行从小到大排序。然后用 i 代表第 i 个活动， s[i] 代表第 i 个活动开始时间，f[i] 代表第 i 个活动的结束时间。按照从小到大排序，挑选出结束时间尽量早的活动，并且满足后一个活动的起始时间晚于前一个活动的结束时间，全部找出这些活动就是最大的相容活动子集合。

背包问题（部分背包）*

将所有待选择物品按照顺序排列，贪心地选择放入最大单位价值物品，如果放不下，将其分割一部分放入背包。

哈夫曼编码

设需要编码的字符集为 $d_1, d_2, ..., d_n$ ，他们出现的频率为 $w_1, w_2, ..., w_n$ 。以 $d_1, d_2, ..., d_n$ 作为叶结点， $w_1, w_2, ..., w_n$ 作为叶结点的权值，构造一颗哈夫曼树。

将 $d_1, d_2, ..., d_n$ 按照出现频率排序，循环遍历 n - 1 次，每次取出出现频率最小的两个组成一个新的结点，放入原排序序列中。
循环过程中构建出树（组合而成的结点就是父结点）
左分支是 0, 右分支是 1, 从根节点到每个叶结点所经过的路径组合成的序列就是该叶结点对应字符的编码。

最小生成树

无向连通图的最小生成树为边权和最小的生成树，求解方式

将图中的边按权值大小排序
从权值小的边开始遍历，如果这条边所连接的两个点在结果集合中没有被连接，则将这条边加入结果集合。

单源最短路径

Dijkstra 算法

构造 dijkstra_list[]，其中存储着每一个点到源点的最短距离。构造的过程中，不是 bfs，而是每次访问距已访问过结点最近的结点。

回溯法

画解空间树

边代表做出的选择
结点代表做出选择后的状态

剪枝：如果要求解最优解，在达到某一个中间状态时发现已经不可能达到一个更优的解时停止搜索。搜索方式常用 dfs。