笔记仓库链接：0000-复习课

第 1 章

1 . 什么是算法

算法是解决问题的一种方法，是由若干条指令组成的有穷序列

2 . 算法与程序的区别有哪些

算法是满足以下性质的指令序列：

输入：零个或者多个外部量作为算法的输入
输出：至少产生一个量作为输出
确定性：组成算法的指令是清晰、无歧义的
有限性：指令数量、执行时间有限

程序是某种程序语言的具体实现，可以不满足有限性

3 . 算法设计与分析的具体步骤是什么

问题定义→选择设计策略→设计算法→证明正确性→分析算法→设计程序

4 . 记号的含义与关系

渐进意义下的记号： $O, Ω, Θ, o, ω$ $g (n)$ 是定义在正数集上的整函数。 $T (n)$ 为算法的时间复杂性， $n$ 是数据规模

渐进上界记号 $O$ ---- ⇐ 若 $T (n) = O (g (n))$ 含义：算法在任何实例情况下，其==时间复杂性不超过 $g (n)$ 的阶数== 即 $lim_{n \to \infty} \frac{T _{ma x} ( n )}{g ( n )} = c \neq = 0, c 为常数$ 如插入排序： $T (n) = O (n^{2})$
渐进下界记号 $Ω$ ---- >= 若 $T (n) = Ω (g (n))$ 含义：算法在任何实例的情况下，其==时间复杂性的阶不低于 $g (n)$ 的阶== 即 $lim_{n \to \infty} \frac{T _{min} ( n )}{g ( n )} = c \neq = 0, c 为常数$ 如插入排序： $T (n) = Ω (n)$
记号 $Θ$ ---- == 算法最好最坏的情况下时间复杂度相同，这就是 $Θ$ 的含义
非紧渐进上界记号 $o$ ---- < 若 $T (n) = o (g (n))$ 含义：算法在任何实例情况下，其==算法时间复杂性的阶小于 $g (n)$ 的阶== 即 $lim_{n \to \infty} \frac{g ( n )}{T _{ma x} ( n )} = 0$ 举例： $g (n) = n^{2}, T_{ma x (n)} = c_{2} n lo g n \to T (n) = o (n^{2})$
非紧渐进下界记号 $ω$ ---- > 若 $T (n) = o (g (n))$ 含义：算法在任何实例情况下，其==算法时间复杂性的阶大于 $g (n)$ 的阶== 即 $lim_{n \to \infty} \frac{T _{min} ( n )}{g ( n )} = \infty$ 举例： $g (n) = n, T_{min (n)} = c_{1} n lo g n \to T (n) = o (n)$

关系： 定理 1: 即渐进上下界相等时性质： image.png|600

5. 递归树、主定理求时间复杂度

主定理求解方法

首先根据 $$ T(n)=\begin{cases} O(1) &n=n_{0} \ aT\left( \frac{n}{b} \right)+f(n) & n>n_{0} \end{cases}\Rightarrow n^{\log_{b}a}

2. 根据 $n^{\log_{b}a}$ 和 $f(n)$ 的阶的关系==（>, =, <）==, 确定使用那种规则 *规则 1*: 如果 $f(n)=O(n^{\log_{b}a-\varepsilon})$, $\varepsilon>0$ 为常数，则 $T(n)=O(n^{\log_{b}a})$ *规则 2*: 如果 $f(n)=\Theta(n^{\log_{b}a})$，则 $T(n)=O(n^{\log_{b}a}\log n)$ *规则 3*: 如果 $f(n)=\Omega(n^{\log_{b}a+\varepsilon})$, $\varepsilon>0$ 为常数，且存在 $n_{0}$, 当 $n>n_{0}$ 时, $af\left( \frac{n}{b} \right)\leq cf(n)$ 成立，$c<1$ 为常数，则 $T(n)=O(f(n))$ > 不是所有的递归方程，都有上述规则， > 主定理方程不是万能的，有条件限制 > > ==先比较阶次再看用哪一条规则== > 规则 1、2 有一个条件需要满足 > 其中规则 3 有两个条件 **例 1: 第二章棋盘覆盖的时间复杂性** 时间复杂性递归定义：$$T(n)=\begin{cases} 1 & n=1 \\ 4T\left( \frac{n}{2} \right)+1 &n>1 \end{cases}$$ > $n^{\log_{b}a}=n^{\log_{2}4}=n^2$, $f(n)=1 \rightarrow n^{\log_{b}a}>f(n)$ > 因为：$f(n)=O(n^{\log_{b}a-2})=O(n^{2-2})$, 这里 $\varepsilon=2>0$ > 根据 Master 定理规则 1: $T(n)=O(n^{\log_{b}a})=O(n^2)$ **例 2: 第二章归并排序的时间复杂性** 时间复杂性的递归定义如下

T(n)=\begin{cases} 1 & n=1 \ 2T\left( \frac{n}{2} \right)+n &n>1 \end{cases}

> $n^{\log_{b}a}=n^{\log_{2}2}=n,f(n)=n\rightarrow n^{\log_{b}a}=f(n)$ > 因为：$f(n)=\Theta(n^{\log_{b}a})=\Theta(n)$ > 根据 Master 定理规则 2: $T(n)=O(n^{\log_{b}a}\log n)=O(n\log n)$ **例 3:** 时间复杂度定义：

T(n)=\begin{cases} 1 & n=1 \ 4T\left( \frac{n}{2} \right)+n^3 &n>1 \end{cases}

> $n^{\log_{b}a}=n^{\log_{2}{4}}=n^2, f(n)=n^3\Rightarrow n^{\log_{b}a}<f(n)$ > 因为：$f(n)=\Omega (n^{\log_{b}a+1}=\Omega(n^{2+1}))$, 这里 $\varepsilon=1>0$ > 并且 $n>1$ 时，$4f\left( \frac{n}{2} \right)=4\left( \frac{n}{2} \right)^3=\frac{n^3}{2}<cf(n)=cn^3$，这里 $\frac{1}{2}\leq c<1$ > 根据 Master 定理的规则 3: $T(n)=O(f(n))=O(n^3)$ **不能使用主定理求解的例子** 并不是所有的递归算法都能使用 master 定理 ![image.png|600](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250703220115429.png) ### 递归树方法 - 递归树是迭代计算模型 - 递归树的生成过程与迭代过程一致 - 更具递归定义不断拓展递归树，指导边界条件（其值已知） - 对递归树产生的所有项求和就是递归方程的解 **例 1:** ![image.png|800](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250704075357541.png) ![image.png|800](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250704075851150.png) > 根据递归式对 n 进行分解，最底层 n=1；把所有层的和加起来得到结果 > 如上，每一层和是 n，层数为 $\log n$，所以 $T(n)=O(n\log n)$ > > 把 f（n）放到母节点上，把他的子问题放到子节点上，依次拓展到子节点为 1> **例 2** ![image.png|800](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250704080956159.png) > 这里母节点 f (n)=1, 子问题问题是 4 个 $T\left( \frac{n}{2} \right)$，子问题的 f（n）也是 1，这样形成了全是 1 的 4 叉树，子问题规模每一次减半，所以树高为 logn；所有层求和得总的时间复杂性 $T(n)=O(n^2)$ **例 3** ![image.png|800](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250704081435836.png) > 母节点 f（n）=n, 每层两分叉，$T\left( \frac{2n}{3} \right)$ 这一分支会更深一点，导致到后面的层，整层的和到不了 n，以为另一分支会提前结束。 > 我们为了方便计算，适当放大一点，把最后的层都看作和为 n > > 层数：$k=\log_{\frac{3}{2}}n$ > $T(n)=kn-n\log_{\frac{3}{2}}n=O(n\log n)$ # 第 2 章 ## 1 . 分治法能解决的问题一般具有哪些特征 1. 该问题的规模缩小到一定的程度就可以容易的解决 2. 该问题可以分解成若干个规模较小的相同问题 3. 利用该问题分解出的子问题的解可以合并为该问题的解 4. 该问题所分解出的各个子问题是相互独立的 > PS: > 其中 2，3 条表明子问题的最优解和该问题的最优解是一致的，这是==最优子结构性质==； > 第 4 条表明，分解出来的子问题是不重复的，共同组成该问题的解，这是==无重复子问题== > > 最优子结构性质和无重复子问题是分支法所能解决问题的必备要素 ## 2 . 二分搜索算法实现与时间复杂度分析 ## **二分搜索技术** 非递减序的 n 个元素 $a[0:n-1]$，现在要在这个元素众找出一特定元素 x 分析： 初始用 l、r 分别表示整个数组最左边和最右边的数据索引 一个子问题 $a[l:r]$，r<l 是表示没有任何元素，返回-1 - 设在 $a[l:r]$ 中找到 x，mid=(l+r)/2 1. 如果 $x==a[mid]$，则找打 2. 如果 $x<a[mid]$，继续在 $a[l, mid]$ 中找 x 即可，即令 r=mid 3. 如果 $x>a[mid]$，继续在 $a[mid,r]$ 中找 x 即可，即令 l=mid 子问题的答案就是大问题的答案，满足分支的四个适用条件 **算法描述** ![image.png](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250704100009249.png) **递归算法时间复杂度分析** 时间复杂性的递归方程

T(n)=\begin{cases} 1 &n=0 \ T\left( \frac{n}{2} \right)+1 &n>1 \end{cases}

利用主定理或递归树可以求其时间复杂性为 $O(\log n)$ **非递归算法时间复杂性分析** 每执行一个循环，问题规模减半，即使最坏情况下，==时间复杂性为 $O(\log n)$== 虽然时间复杂度非递归方案和递归方案一样，但是非递归方案效率更高 ## 3 . 棋盘覆盖问题，回溯法、栈、队列求解的实例 **棋盘覆盖问题** 在一个 $2^k\times 2^k$ 个方格组成的棋盘之中，恰有一个方格与其他方格不同，成该方格为-特殊方格。且称该棋盘为-特殊棋盘。棋盘覆盖问题中，要用图示的 4 中不同形态的 L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何 2 个 L 型骨牌不得重叠覆盖 ![image.png](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250704174707365.png) **思路** 当 k>0 是，将 $2^k \times 2^k$ 棋盘分割为 4 个 $2^{k-1}\times2^{k-1}$ 子棋盘（a）所示。特殊方格必位于较小子棋盘之中，其余 3 个子棋盘中无特殊方格。为了将这 3 个无特殊方格的子棋盘转化为特殊棋盘，可以用 L 型骨牌覆盖这 3 个较小棋盘的会合处，如图（b）所示，从而将原问题转化为 4 个较小规模的棋盘覆盖问题。递归的使用这种分割，直到棋盘简化为棋盘 $1\times 1$ ![image.png](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250704175939338.png) > 原棋盘分割成 4 个，在三个无特殊方格的棋盘添加一个 L 型骨牌，问题变成了 4 个和原问题相同性质的 4 个子问题 **算法描述** ![image.png](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250704180205190.png) > 其中 tr，tc 是左上角坐标，dr，dc 是特殊方格坐标，size 是棋盘大小, s 是子棋盘大小 > 四个 if 对应特殊方格在不同子棋盘中的情况 **时间复杂性**

T(n)=\begin{cases} O(1) & n=1 \ 4T\left( \frac{n}{2} \right)+O(1)&n>1 \end{cases}

由主定理规则 1 ，可得时间复杂性 $T(n)=O(n^2)$ *本算法可使用队列或者栈实现非递归算法* ### 拓展 **队列实现** 队列先入先出 入队：一个大棋盘分为四个子棋盘，将四个子棋盘按序入队 出队：从队列中取出一个棋盘，将其分为四个子棋盘 注意：划分为四个子棋盘时，一个 L 型块被放入到棋盘中 **栈实现** 栈先入后出 入栈： 大棋盘分为四个子棋盘，将四个子棋盘按序入栈 出栈：从栈顶取出一个棋盘，将其分为 4 个子棋盘 注意：划分为四个子棋盘时，一个 L 型块放到棋盘中 ## 4 . 合并排序算法实现与时间复杂度分析 **合并排序** 将待排序元素集合分成大小大致相同的 2 个子集合，分别对 2 个子集合进行排序，最终将排好序的子集合合并成一个有序结合 **算法实现（递归）** ```cpp void MergeSort(Type a[], int left, int left) { if (left < right) // 至少两个元素 { int i=(left+right)/2; //取中点 MergeSort(a, left, i); // 左半部分 MergeSort(a, i+1, right); // 右半部分 merge(a, b, left, i, right); //两个部分排序合并， 放到临时数组b中 copy(a, b, left, right); // 把数组b复制回 数组a } } ``` **复杂度分析**

T(n)=\begin{cases} O(1) & n\leq 1 \ 2T\left( \frac{n}{2} \right)+O(n) & n>1 \end{cases}

$T(n)=O(n\log n)$ 渐进意义下的最优算法 ## 5 . 快速排序时间复杂度分析 **快速排序算法的时间复杂型分析** - 快速排序算法的性能取决于划分的对称性 最坏的情况：每次划分成 2 个子问题，一个长度为 0. 另一个长度为 n-1，其对应的递归定义为： $$ T(n)=\begin{cases} 1 & n=1 \\ T(n-1)+n &n>1 \end{cases}

最坏的时间复杂度：$O(n^2)$
平均时间复杂度：$O(n\log n)$
稳定性：不稳定

第 3 章

1. 动态规划算法求解的基本步骤

找出最优解的性质，并刻画其结构特征（最优子结构性质）
递归的定义最优值
以自底而上的方式计算出最优值
根据计算最优值时得到的信息，构造最优解

2. 动态规划与分治法的区别

相同点：

当问题规模较小的时候, 答案直接可得或者很容易解决
问题可分
小问题答案可以合并成大问题答案

不同点:

动态规划解决的问题存在大量重复，分治的子问题相互独立

3. 矩阵连乘问题算法与实例

矩阵连乘问题描述

给定 n 个矩阵 ${A_{1}, A_{2}, \dots, A_{n}}$ ，其中 $A_{i}$ 与 $A_{i + 1}$ 是可乘的， $i = 1, 2 \dots, n - 1$ . 考查这 n 个矩阵的连乘积 $A_{1} A_{2} \dots A_{n}$
由于矩阵乘法满足结合律，所有计算矩阵的连乘可以有许多不同的计算次序。这宗计算次序用加括号的方式确定
若一个矩阵连乘积的计算次序完全确定，也就是说该乘积已完全加括号，则可以依次序反复调用两个矩阵相乘的标准算法计算出矩阵连乘积

如何确定计算次序，抱枕需要的连乘次数最少？ 穷举法 列出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次序，从中找出一种数乘次数最少的计算次序 穷举法-算法复杂性分析 N 个矩阵的连乘积，设不同的计算次序为 $P (n)$ . 因每种括号方式都可以分解成两个子矩阵的加括号问题： $(A_{1} \dots A_{k}) (A_{k + 1} \dots A_{n})$ , 故 $P (n)$ 的递推式如下：

P (n) = {1 \sum_{k = 1}^{n - 1} P (k) P (n - 1) n = 1 n > 1 \Rightarrow P (n) = Ω (\frac{4 ^{n - 1}}{\frac{( n - 1 ) ^{3}}{2}})

可以发现穷举法计算复杂度非常高，这种方案不可行

动态规划

1 . 首先分析最优解的结构

考查计算 A[i, j]的最优计算次序，设这个计算次序在矩阵 $A [k]$ 和 $A [k + 1]$ 之间段考， $i \leq k < j$ 则其相应完全加括号方式为 $(A_{i}, A_{i + 1} \dots, A j) = ((A_{i}, A_{i + 1}, \dots, A_{k}) (A_{k + 1}, A_{k + 2}, \dots, A_{j}))$

这样这个问题就被划分成了两个子问题

特征：计算 $A [i : j]$ 的最优次序所包含的计算矩阵子链 $A [i : k]$ 和 $A [k + 1 : j]$ 的次序也是最优的
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。可用动态规划算法求解的显著特征

$A [i]$ 的维数是 $P_{i - 1} \times P_{i}$ $m [i, j]$ 表示 $A [i : j]$ 的计算量 $A [i : k]$ 的计算量为 $m [i : k]$ $A [k + 1 : j]$ 的计算量为 $m [k + 1 : j]$

因此： $m [i, j] = m [i, k] + m [k + 1, j] + P_{i - 1} \times P_{k} \times P_{j}$

反证法可证明 $m [i, j]$ 是最优的，则 $m [i, k], m [k + 1, j]$ 一定也是最优值（ $P_{i - 1} \times P_{k} \times P_{j}$ 常数）

2 . 建立递归关系（最优递归关系）

m [i, j] = {0 mi n_{i \leq k < j} {m [i, k] + m [k + 1, j] + P_{i - 1} P_{k} P_{j}} i = j i < j

这里递归的时，需要找到 k 的值保证 $m [i, j]$ 最小

3 . 以自底向上的方式求最优解

对于 $1 \leq i \leq j \leq n$ 不同的有序对 $(i, j)$ 对应不同的子问题。因此，不同子问题的个数共有：$$ \left(\begin{array}{ll} n \ 2 \end{array}\right)+n=\Theta(n^2)

- 动态规划算法解此问题，可以举其递归式以自底向上的方式进行计算 - 保存已保存的子问题答案，每个子问题值计算一次，需要是只要查一下子问题的结果，避免大量重复计算，最终得到多项式时间的算法 **算法描述** ![image.png](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250706094703838.png) > 先初始化 $m[i][i]$ =0, 代表只有一个矩阵时，相乘次数为 0 > 同时为计算规模为 2 的矩阵乘法，创造条件；此时 $m[i][j]=m[i][j+1]=0+0+p[i-1]*p[i]*p[j]$ > 这也为规模为 3 的矩阵乘法创造了条件，一次完成所有矩阵相乘的规模 > $s[i][j]=i$ 代表当前划分节点是 i，即 i 到 j 之间所有矩阵相乘 > For 循环从 i+1 到 j-1, 即把 i 到 j 的连乘矩阵从中间拆开，拆开的都是更小规模的问题，可以利用 m 中乘的次数计算出在当前维持拆开需要的乘法的次数，遍历到其中更小的计算次数，把拆开的节点更新到 k 中 **算法复杂度分析** 算法主要计算量取决于算法中子问题的数量（应为需要把所有子问题的乘法次数算出来），已知为 $O(n^2)$，求每个子问题的最优值的时间复杂性 $O(n)$（即 k 控制得循环次数最大值），==因此算法的计算时间上界==为 $O(n^3)$. 算法所占用的==辅助空间==显然为 $O(n^2)$ (m 数组大小) **计算过程示例** ![image.png](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250706101136858.png) > 对照代码，先计算出 $m[i][j]$ 的值。然后找到从 i 到 j 之间断开的乘法次数最小值，即代码中 k 控制的 for 循环 > $s[i][j]$ 中保存了从 i 到 j 的连乘矩阵从那里断开，乘法次数最小 ### 4 . 递归算法构造最优解 用来把得到的 S 中的结果，展示出来 **递归算法打印最优解** ```cpp void Traceback(int i, int j, int **s) { if (i==j) return ; //只有一个矩阵 Traceback(i, s[i][j], s); //断开之后，左半部分 Tracebacj(s[i][j]+1, j, s); //断开之后，右半部分 cout<<i<<","<<s[i][j]; cout << "and" << s[i][j]+1<<","<<j<<endl; } ``` ## 4. 最长公共子序列问题算法与实例 **最长公共子序列** ![image.png](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250707080920671.png) ### 1 . 最长公共子序列的结构 ![image.png](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250707081542992.png) > 这里从后向前，如果元素相同，一定是这个序列的最后一个元素 > 不相等分两种情况，其中一个序列的最后一个匀速不再公共子序列，需要去掉 > 当递归计算时，这两种情况也会包含两个序列最后一个元素都需要去掉的情况 > > 可见，2 个序列的最长公共子序列包含了这 2 个序列的前缀的最长公共子序列。因此，最长公共子序列问题有==最优子结构性质== ### 2 . 最优值的递归定义 用 $c[i][j]$ 记录序列的最长公共子序列的长度。其中：$X_{i}=\{x_{1},x_{2},\dots,x_{i}\};Y_{j}=\{y_{1},y_{2},\dots, y_{j}\}$ 递归关系如下：$$c[i][j]=\begin{cases} 0 & i=0|j=0 \\ c[i-1][j-1]+1&i,j>0;x_{i}=y_{i} \\ max\{c[i][j-1],c[i-1][j]\} &i,j>0;x_{i}\neq y_{i} \end{cases}$$ ### 3 . 自底向上的方式求最优值 在所考虑的子问题空间中，总够有 $\theta(mn)$ 个不同的子问题 ![image.png](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250707083418172.png) > 这里 $c[i][j]$ 是表示长度为 i 和长度为 j 的序列的最长子序列的长度，他是从 $c[0][0]$ 开始一步一步向前计算出来的；他是一个记录状态的动态规划表格 > > 其中 b 是辅助构造最优解的信息表，记录 $c[i][j]$ 状态是从那个状态转变过来的 > > 中间判断又分为三种情况 > 1. 当前字符相同 $x[i][==y[j]]$, 此时最长公共子序列加了一个字符，他是从 $c[i-1][j-1]$ 这个状态过来的 > 2. 当两个字符不相等，他们需要从 $c[i-1][j]$ 和 $c[i][j-1]$ 这两个状态中选择一个更长的长度保存 ### 4 . 构造最优解 ![image.png|500](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250707085303636.png) > 根据状态转移的标记，倒着找到最大子序列中的元素 **例子** ![image.png](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250707090303613.png) ## 5. 0-1 背包问题算法与实例 **0-1 背包-动态规划** ![image.png](https://cdn.jsdelivr.net/gh/AustinSuun/image/img/20250709081131042.png) > $x_{i}$ 代表是否取这个物品，$x_{i}=1$ 代表选择这个物品 ### 1. 最优子结构性质分析 考虑前 i 个物品装入容量为 j 个背包所能获得的最大价值用 $m[i][j]$ 表示 - 当第 i 个物品重量 $w_{i}$ 超过背包容量 j 时，第 i 个物品不能装入，实际上：$m[i]][j]=m[i-1][j]$ - 当第 i 个物品重量 $w_{i}$ 不超过背包容量是，第 i 个物品可装可不装。因此 $m[i][j]=max(m[i-1][j],m[i-1][j-w_{i}]+v_{i})$ 可见：该问题具有最优自己子机构性质，即大问题最优子结构包含了子问题的最优解 ### 2. 最优值递归定义 - 当把第一个物品装入背包为 j。即边界条件

m(1,j)=\begin{cases} v_{i}&j\geq w_{1} \ 0 &0 \leq j<w_{1} \end{cases}

- 当把前 i 个物品装入背包为 j 。即一般强况， i > 1

m(i,j)=\begin{cases} max{m(i-1, j),m(i-1, j-w_{i})+v_{i}} & j\geq w {i} \ m(i-1, j) &0\leq j<w{i} \end{cases}

人杰地灵东箭南金

探索

0000-复习课