考研复试 算法设计与分析 笔试笔记

大O记号

$n \to \infty$ 时，$f(n)$ 不会快于 $g(n)$

如果存在正数$c$和$n_0$，使得当$n \geq n_0$时，有$f(n) \leq cg(n)$，则称$f(n)$是$O(g(n))$的。
$c$和$n_0$怎么找？系数加一。
简单地说，如果$f(n)$最高项为一次项（例如$3n+2$），那么就把常数项放掉，看$n$等于几时$f(n)$的值开始小于$4n$。
如果$f(n)$既有一次项又有二次项（例如$3n^2+2n+1$），那么首先把常数项放掉，看$n$等于几时$f(n)$的值开始小于$3n^2+3n$；再把一次项放掉，看$n$等于几时$f(n)$的值开始小于$4n^2$。

p19 例2-2 证明$f(n) = 10n^2 + 4n + 2 = O(n^2)$
解：
$n\geq 2$时，有$10n^2 + 4n + 2 \leq 10n^2 + 5n$
$n\geq 5$时，有$5n \leq n^2$
取$n_0 = 5$，$c = 11$，则当$n\geq n_0$时，有$f(n) \leq 11n^2$，所以$f(n) = O(n^2)$.

大Omega记号

$n \to \infty$ 时，$f(n)$ 不会慢于 $g(n)$

如果存在正数$c$和$n_0$，使得当$n \geq n_0$时，有$f(n) \geq cg(n)$，则称$f(n)$是$\Omega(g(n))$的。
$c$和$n_0$怎么找？最高次系数不动，小的全放掉。

p20 例2-6 证明$f(n) = 10n^2 + 4n + 2 = \Omega(n^2)$
解：
对所有$n$，有$10n^2 + 4n + 2 \geq 10n^2$
取$n_0 = 1$，$c = 10$，则当$n\geq n_0$时，有$f(n) \geq 10n^2$，所以$f(n) = \Omega(n^2)$.

综合比较两个函数的时间复杂度

基本思路： 如果$f(n)$是$\Omega(\text{某个函数})$的，同时$g(n)$又是$O(\text{某个函数})$的，那么$f(n)$就是$\Omega(g(n))$的。

p29 习题2-11(2) $f(n)=n^2/\log n$，$g(n)=n\log^2 n$
解：

1. 取$n_0 = 2, c=\frac{1}{2}$，对于所有$n\geq n_0$时，有$\log n \geq 1$
   因此 $f(n) \geq \frac{1}{2}n^2$，所以$f(n) = \Omega(n^2)$.
2. 取$n_0 = 1, c = 1$，对于所有$n\geq n_0$时，有$\log^2 n \leq n$
   因此 $g(n) \leq n*n = n^2$，所以$g(n) = O(n^2)$.
3. 由(1)和(2)可得$f(n) = \Omega(g(n))$。

2.4.1 单循环

int i=0;
while (i*i*i <= n)
    i++;

$T = O(\sqrt[3]{n})$

int i=1;
while (i<=n)
    i = i * 2;

$T = O(\log n)$

x=0;
while (n >= (x+1)*(x+1))
    x++;

$T = O(\sqrt{n})$

i = n*n;
while (i != 1)
    i = i / 2;

$T = O(\log n)$

2.4.2 两重循环

int m=0, i, j;
for (i=1; i<=n; i++)
    for (j=1; j<=2*i; j++)
        m++;

$T = O(n^2)$

for (i=0; i<n; i++)
    for (j=0; j<m; j++)
        A[i][j] = 0;

$T = O(mn)$

count = 0;
for (k=1; k<=n; k*=2)
    for (j=1; j<=n; j++)
        count++;

$T = O(n \log n)$

for (i=n-1; i>=1; i--)
    for (j=1; j<i; j++)
        if (A[i] > A[j+1])
            swap(A[i], A[j]);

$T = O(n^2)$

6.3.1 朴素算法

思路：优先安排收益最高的作业，尽可能将其安排在最晚的可用时间点，从而为其他作业预留更多的早期时间段。

1. 按收益 $p_i$ 从大到小排序
2. 按顺序遍历所有作业
3. 从其截止时间向前查找可用时间 分配给该作业，若无空闲时间则跳过该作业。

首先按收益排序：

• 作业1：(2, 100)
• 作业4：(1, 27)
• 作业3：(2, 15)
• 作业2：(1, 10)

依次处理：

• 作业1(100)：可以安排在时间2
• 作业4(27)：可以安排在时间1
• 作业3(15)：没有可用时间，跳过
• 作业2(10)：没有可用时间，跳过
• 最终获得的最大收益为：100 + 27 = 127

习题6-3

最优解 5 6 3 2
最大收益 74

6.3.2* 改进算法

待补充

6.4.1 最佳两路合并模式（哈夫曼编码）

就是哈夫曼树求最小 WPL（带权外路径长度）

(20,30,30,10,5)

WPL = (5+10)*3 + (20+30+30)*2 = 205

6.4.2* 三(k)路合并 书p105/习题6-8

https://www.bilibili.com/video/BV1tucQeQECb

补：虚节点，数量为 $(k-1) - (n-1) \% (k-1)$ 个
(3, 7, 8, 9, 15, 16, 18, 20, 23, 25, 28) => n=11,k=3, (n-1)%(k-1)=0，不用补；
(1, 2, 3, 3, 5, 6, 7 ,9) => n=8,k=3,(n-1)%(k-1)=1，补1个虚节点；WPL=66

6.5.1 Prim

适用于稠密图 每次从已有点集合里扩展出一条最短的边

• 使用邻接矩阵时，时间复杂度 $O(V^2)$
• 使用邻接表 和优先队列 时，时间复杂度 $O(E*logV)$

6.5.2 Kruskal

适用于稀疏图 对边从小到大排序，依次加入边，每次加入都需要判环路

• 时间复杂度 $O(E*logE)$

习题6-9

明显是稠密图，选 Prim

6.7.1 单带最优存储

说人话：
把 $n$ 个程序（线段）按某种顺序排列在一个磁带（数轴）上，程序不能重叠，保证磁带能放得下所有程序，要求平均检索时间（MRT）最小。 MRT = 所有程序的检索时间之和 $\div$ 程序个数
由于程序个数固定，所以 MRT 最小等价于检索时间之和最小。
检索时间 = 程序起点到磁带起点距离 $+$ 程序长度
每次检索都从磁带起点开始，所以离起点越远的程序检索时间越长。
各种排列方式参考：书p117 表6-5

贪心策略：按程序长度从小到大排序，依次放入磁带。

6.7.2 多带最优存储

现在磁带变成了 $m$ 个，其实也很简单：将程序$0$放在第一个磁带上，程序$1$放在第二个磁带上，程序$2$放在第三个磁带上…当 $m$ 个磁带都排完一遍，回到第一个磁带，继续顺次放程序。

#include <iostream.h>
void Store(int n, int m)     
{
     int j = 0; 
     for (int i=0; i<n; i++) { 
        cout << "将程序"<<i<<" 加到磁带" <<j<<endl; 
        j=(j+1)% m; 
     } 
     cout<<endl;
}

7.2.1 递推关系

设 $D^{(k)}[i][j]$ 表示从节点 $i$ 到节点 $j$ 且中间节点编号不超过 $k$ 的最短路径长度。

递推关系：对于每个中间节点 $k$，有两种情况：

1. 不经过 $k$：路径保持原值，即 $D^{(k)}[i][j] = D^{(k-1)}[i][j]$
2. 经过 $k$：路径拆分为 $i \to k$ 和 $k \to j$，即 $D^{(k)}[i][j] = D^{(k-1)}[i][k] + D^{(k-1)}[k][j]$ 实际实现中，我们可以将 $k$ 从 0 到 n 枚举，覆盖更新，就不再需要 k 这一维了。

简化版的状态转移：

$D[i][j] = \min\left(D[i][j], D[i][k] + D[k][j]\right)$

伪代码： 枚举顺序 $k \to i \to j$

for k: 0->n
    for i: 0->n
        for j: 0->n
            if(i~k~j 小于 i~j)
                d[i][j] = d[i][k] + d[k][j]

7.2.2 记录路径

引入一个额外的二维数组 next，其中 next[i][j] 表示从节点 $i$ 到节点 $j$ 的最短路径中，$i$ 的下一个节点。

• 初始化：

  • 如果 $i$ 和 $j$ 之间有边，则 next[i][j] = j
  • 否则，next[i][j] = -1

• 更新规则：

  • 当发现更短的路径时，更新 dist[i][j] 和 next[i][j]
  • next[i][j] 被设置为 next[i][k]，因为路径从 $i$ 经过 $k$ 到 $j$

• 路径打印：

  • 使用 next 数组回溯路径，从 $i$ 开始，沿着 next 数组直到 $j$

假设图的邻接矩阵如下：

调用 floyd 算法后，dist 和 next 数组如下：

代码演示（gpt-4o-mini生成，可以丢给AI解释）

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

void floydWarshall(int n, vector<vector<int>>& graph, vector<vector<int>>& dist, vector<vector<int>>& next) {
    // Initialize distance and next matrices
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            dist[i][j] = graph[i][j];
            if (graph[i][j] != INF && i != j) {
                next[i][j] = j;
            } else {
                next[i][j] = -1; // No path
            }
        }
    }

    // Floyd-Warshall algorithm
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];
                }
            }
        }
    }
}

void printPath(int u, int v, const vector<vector<int>>& next) {
    if (next[u][v] == -1) {
        cout << "No path from " << u << " to " << v << endl;
        return;
    }
    cout << "Path from " << u << " to " << v << ": ";
    while (u != v) {
        cout << u << " ";
        u = next[u][v];
    }
    cout << v << endl;
}

int main() {
    int n = 4; // Number of vertices
    vector<vector<int>> graph(n + 1, vector<int>(n + 1, INF));
    vector<vector<int>> dist(n + 1, vector<int>(n + 1));
    vector<vector<int>> next(n + 1, vector<int>(n + 1));

    // Example graph initialization (0: no edge, INF: no path)
    graph[1][1] = 0;
    graph[1][2] = 3;
    graph[1][3] = INF;
    graph[1][4] = 7;
    graph[2][1] = 8;
    graph[2][2] = 0;
    graph[2][3] = 2;
    graph[2][4] = INF;
    graph[3][1] = 5;
    graph[3][2] = INF;
    graph[3][3] = 0;
    graph[3][4] = 1;
    graph[4][1] = 2;
    graph[4][2] = INF;
    graph[4][3] = INF;
    graph[4][4] = 0;

    floydWarshall(n, graph, dist, next);

    // Print final path and distance matrices
    cout << "Distance Matrix:" << endl;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (dist[i][j] == INF) {
                cout << "INF ";
            } else {
                cout << dist[i][j] << " ";
            }
        }
        cout << endl;
    }

    cout << "Path Matrix:" << endl;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cout << next[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

7.3.1 普通动态规划

自底向上：通过 迭代 预先计算所有可能的子问题，按子链长度从小到大的顺序填充表格。

记 $m[i][j]$ 为从 i 到 j 最少乘法次数，那么：

• 对 $i \sim j$ 中任意一个数 $k$，$m[i][k], m[k+1][j]$ 也都是最少的 [最优子结构性质]
• $m[i][i]=0$ [一个矩阵不用做乘法]
• 当 $i < j$ 时，$m[i][j]= min \{ m[i][k] + m[k+1][j] + \text{(一次乘法操作)} \}$，其中 $i \leq k < j$

(一次乘法操作)= $p_i*q_k*q_j$ 根据本节开头提到的性质，(一次乘法操作)可以改写为 $q_{i-1}*q_k*q_j$。 这样改写的好处是，矩阵可以简化为用一维数组保存。

7.3.2 备忘录方法

自顶向下：通过 递归 分解问题，遇到子问题时先查表，若未计算则递归求解并保存结果，按需填充表格。

记 $m[i][j]$ 为从 i 到 j 最少乘法次数，$Memo(i, j)$ 从 i 到 j 最少乘法次数的递归函数，那么：

• $m[i][i]=0$ [一个矩阵不用做乘法]
• 其他的 $m[i][j]$ 均初始化为 -1
• 如果 $m[i][j] \neq -1$ 说明子问题已经计算过，直接返回
• 当 $i < j$ 时，$m[i][j]= Memo(i, k) + Memo(k+1, j) + \text{(一次乘法操作)}$

上述两种方法时间复杂度都是 $O(n^3)$，空间复杂度都是 $O(n^2)$

7.6.1 一般方法

设背包容量6，物品如下：

记 $dp[i][j]$ 表示仅能在前 i 件物品里面选、放入大小为 j 的背包中，得到的最大价值。例题要求的就是 $dp[5][6]$.

状态如何转移？

1. $dp[i][0] = dp[0][j] = 0$，没有物品/背包容量为0，肯定没有价值
2. $j < w[i]$，背包的容量装不下第 i 件物品，选不了第 i 件物品。 $dp[i][j] = dp[i-1][j]$
3. $j >= w[i]$，背包的容量能装下第 i 件物品，此时考虑选不选第 i 件。 $dp[i][j] = max(\text{选第i件}, \text{不选第i件})$
4. 若选第 i 件，价值为 (第 i 件物品的价值) + (前 i-1 件物品、放入去掉第 i 件物品重量的背包、得到的最大价值)
   即 $dp[i-1][j-w[i]] + v[i]$
5. 若不选第 i 件，价值就还是 $dp[i-1][j]$

时间复杂度：$O(nm)$，其中n表示物品的数量，m表示背包的容量

7.6.2* 阶跃点法

https://www.bilibili.com/video/BV1ZNcUeoEuk

阶跃点（Step Points） 表示在不同背包容量下，能够达到的最优（重量，价值）组合。
每个阶跃点集合 $S_i$ 表示处理前 $i+1$ 个物品后的状态。

剔除被支配点：两个阶跃点A（W1, V1）和B（W2, V2），如果W1 ≤ W2且V1 ≥ V2，那么B点被支配，应该剔除。
即，A点花费了更少的容量，得到了更大的价值，必定比B点更优。就不要B点了。

设背包容量6，物品如下：

(1) 初始状态 $S^{-1}$（未放入任何物品）

• 初始状态为空背包，仅包含原点： $$S^{-1} = \{(0, 0)\}$$

(2) 处理第0个物品（重量1.8，价值2） → 生成 $S^{0}$

• 不放入物品0：保留 $S^{-1}$ 的所有点 $\{(0, 0)\}$。
• 放入物品0（记为 $S^0_1$）：生成新点 $(1.8, 2)$。
• 合并并剔除被支配的点：
  • 比较 $(0, 0)$ 和 $(1.8, 2)$，均未被支配。
  • 最终集合： $$S^{0} = \{(0, 0), (1.8, 2)\}$$

(3) 处理第1个物品（重量3.2，价值3） → 生成 $S^{1}$

• 不放入物品1：保留 $S^{0}$ 的所有点 $\{(0, 0), (1.8, 2)\}$。
• 放入物品1（记为 $S^1_1$）：对 $S^{0}$ 中的每个点 $(w, v)$，生成新点 $(w+3.2, v+3)$：
  • $(0+3.2, 0+3) = (3.2, 3)$
  • $(1.8+3.2, 2+3) = (5.0, 5)$
• 合并并剔除被支配的点：
  • 原集合 $S^{0}$ $\{(0,0), (1.8,2)\}$ 与新集合 $S^1_1$ $\{(3.2,3), (5.0,5)\}$ 合并。
  • 剔除被支配的点（例如，$(3.2,3)$ 未被任何点支配）。
  • 最终集合： $$S^{1} = \{(0, 0), (1.8, 2), (3.2, 3), (5.0, 5)\}$$

(4) 处理第2个物品（重量2.5，价值5） → 生成 $S^{2}$

• 不放入物品2：保留 $S^{1}$ 的所有点。
• 放入物品2（记为 $S^2_1$）：对 $S^{1}$ 中的每个点 $(w, v)$，生成新点 $(w+2.5, v+5)$：
  • $(0+2.5, 0+5) = (2.5, 5)$
  • $(1.8+2.5, 2+5) = (4.3, 7)$
  • $(3.2+2.5, 3+5) = (5.7, 8)$
  • $(5.0+2.5, 5+5) = (7.5, 10)$（超出容量6，舍去）
• 合并并剔除被支配的点：
  • 原集合 $S^{1}$ $\{(0,0), (1.8,2), (3.2,3), (5.0,5)\}$ 与新集合 $S^2_1$ $\{(2.5,5), (4.3,7), (5.7,8)\}$ 合并。
  • 剔除被支配的点：$(2.5,5)$ 比 $(3.2,3), (5,5)$ 更优。
  • $(5.7,8)$ 是最大价值点。
  • 最终集合： $$S^{2} = \{(0, 0), (1.8, 2), (2.5, 5), (4.3, 7), (5.7, 8)\}$$

(5) 逆序求解选了哪些物品

如果上面的步骤看懂了，直接看视频 5:09

本例答案：

$(5.7,8) \in S^2_1 \text{还是} S^1? ==> S^2_1 \therefore x2=1$
$(3.2,3) \in S^1_1 \text{还是} S^0? ==> S^1_1 \therefore x1=1$
$(0,0) \in S^0_1 \text{还是} S^{-1}? ==> S^{-1} \therefore x0=0$

$x=(x0,x1,x2)= \{ 0,1,1 \}$