算法课程总结

第一章 绪论

算法的特征：

  1. 有穷性/终止性
  2. 确定性
  3. 能行性
  4. 输入
  5. 输出

第二章 计算复杂度

计算复杂性函数的阶

详见notability笔记

第三章 分治法的应用

归并排序，快速排序

最大值最小值

棋盘覆盖

中位数

1506. 中位数 - AcWing题库

详见Divide and Conquer这篇文章

第四章 动态规划

区间dp

矩阵乘法

最优二分搜索树

线性dp

最长公共子序列

背包问题

详见DP汇总这篇文章

第五章 贪心算法

任务安排问题

哈夫曼编码

最小生成树:Prim, Kruskal

关键其实就是对于优化子结构和贪心选择性的证明

第六章 搜索

爆搜：按照一定的顺序，穷举解空间的每种可能，直到找到问题的答案。

一般的搜索形式：深度优先、广度优先

优化：爬山法、best first、分支界限

爬山法是在深搜基础上加了启发式测度贪心，best first是在宽搜基础上加了评价函数，
分支界限是用于有效求解组合优化问题的，其实也就是最优性剪枝。

旅行商问题、A*算法

这块详见搜索与图论这篇文章。

第七章 摊还分析

摊还分析是为了研究数据结构上操作代价的，一个数据结构可能进行很多不同代价的操作，那么平均地来看，对这个数据结构操作的代价是什么捏，如果采用之前的时间复杂度分析，像处理循环语句之类的处理数据结构操作，没考虑到数据结构本身的特点，得出的结论肯定是有问题的，这时就要考虑具体分析的思路了，也就是摊还分析。

摊还分析的方法主要分为：聚集法，会计法，势能法。

聚集法就是针对每个操作，给出相应的代价，然后对于整体的所有操作，进行求和，然后给出一个上界。说白了就是将整体代价拆为一个一个地去算每个操作的代价。

会计法就是给出一个所有操作的摊还代价表，然后就一劳永逸，得出上界。重点是这个表应该怎样去设计，也就是哪些操作要设置余额，设置多少。这个的话就要具体来看数据结构上的操作了，有些操作是往数据结构里面加东西，比如加数加元素，有些则是让数据结构发生一些变化，关键就是要看一些因果关系，某些操作是另一些操作的前提，利用这点去设计余额。

势能法就是把会计法里面的余额当成整个数据结构的势能了，然后这个势能函数的设计是重点，怎么设计捏，和会计法的思路其实差不多，也是去找因果关系的操作，其实就是为了一些开销很大的操作去积累势能。

课上是主要介绍了几个问题：栈操作，二进制计数器和动态表。

稍微特殊一点的可能是二进制计数器，在考虑会计法和势能法的时候要稍微想一下，其实也蛮显然的，会计法的话就这么想，加数字才能产生进位代价，所以加1操作要设置余额，那么到底该设置多少捏，可以这么想，10000000这种1个1然后全是很多个0的，如果只是设置加1代价为2，会出现最后还少一点，所以考虑0->1的摊还代价是2，这样就欧克了。势能法去分析的话，就是要积攒势能为进位提供余额，进位最猛的时候也就是把所有1变成0，所以如果拿所以1的数量当成势能的话，就可以应对所有操作了。

势能法去分析的时候那个实际代价可以是未知的，拿个字母表示一下就行了，算摊还代价的时候是会消掉的。

然后动态表的话，怎么说捏，记住思路和那个收缩的势能方程即可。

第八章 图论算法

单源最短路径、多源最短路径

网络流算法

匹配问题

这块详见搜索与图论这篇文章。

第九章 字符串匹配

朴素匹配

1
2
3
4
5
6
7
8
9
10
11
S[N], p[M];

for(int i = 1; i <= n; i++ ){
    bool flag = true;
    for(int j = 1; j <= m; j++){
        if(s[i] != p[j]){
            flag = false;
            break;
        }
    }
}

指纹匹配

指纹匹配的原理就是通过计算字符串代表的数值大小，进行匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13
T[N], P[M]
fp <- compute (fp);
f <- compute (T[0, m-1]);
flag <- 1;
for(int i = 0 ;i < n - m; i++){
    if(fp == f){
        cout << i << endl;
        flag <- 0;
    }
    f = (f - T[m] * 10^(m-1)) * 10 + T[s+m];
}
if(flag)
return -1;

Rabin-Karp

模式串p太长的时候，会存在溢出，而且大数的比较常常不是O(1)就能完成的，因此考虑优化，也就是用Hash，mod处理，总的来说就是利用Hash的不同排除大部分不同的情况，然后对于Hash相同的就逐一对比。

参考指纹算法的思路，代码其实也长得差不多，只有一些预处理的不同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
T[N], P[M]
//fp <- compute (fp);
//f <- compute (T[0, m-1]);
c <- 10^(m-1) mod q //循环实现
for(int i = 0; i < m;i++){
    fp  = (10 * fp + P[i]) mod q;
    ft  = (10 * ft + T[i]) mod q;
}
flag <- 1;
for(int i = 0 ;i < n - m; i++){
    if(fp == ft){
        cout << i << endl;
        flag <- 0;
    }
    ft = ((ft - T[m] * c) * 10 + T[s+m])mod q;
}
if(flag)
return -1;

有限状态自动机

就是对于模式串已经匹配的个数进行枚举，从0~m，然后针对下一个输入的字符的可能，依次计算出状态转移的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//建表过程
m <- P.length
for q <- 0 to m{
    for each character a in table{
        if(P[0:q]+'a' == P[0:q+1])
            state_trans(q, 'a') <- k + 1;
        else{
             k <- q + 1;
             do k <- k - 1; while(P[0:k] is the suffix of P[0:q]+'a' && k >0);
             state_trans(q, 'a') <- k;
        }
    }
    return state_trans;
}

//匹配过程
flag <- 1;

for i <- 0 to n{
    q <- (q, T[i]);
    if(q == m){
        cout << i << endl;
        flag <- 0
    }
    
}

if(flag)
        return -1

KMP算法

kmp相对于有限状态自动机的改进是充分结合了字符串本身的特性，其实也是类似一种时间换空间，对于不匹配的过程，不是直接给出表的值，而是利用递归去进行处理，节省空间。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//下标从0开始，若k为已匹配数，则ne[k]表示公共最长前后缀最后一个位置的下一个，也就是新的待判断的位置。
#include<iostream>

using namespace std;

const int M = 1e5 + 10, N = 1e6 + 10;
int n, m;
char q[M], s[N];
int ne[M];

int main(void){
    
    cin >> m >> q >> n >> s;
    
    // 求next数组,ne[i]里存的是从0~i-1这么多字符里最大相同前后缀的个数
    for(int i = 2; i <= m; i ++){ //已经匹配了i个
        int k = ne[i - 1];
        while(k > 0 && q[i - 1] != q[k])
            k = ne[k];
        
        if(q[k] == q[i - 1])
            k++;
    
        ne[i] = k;
    }
    
    // 匹配过程
    int t = 0; //匹配的个数
    for(int i = 0; i < n; i++){
        while(t > 0 && q[t] != s[i])
            t = ne[t];
        
        if(q[t] == s[i])
            t++;
            
        if(t == m){
            cout << i - m + 1 << " ";
            t = ne[t];
        }
    }

    
    return 0;
}

朴素逆向

顾名思义，把朴素匹配的循环倒过来就行了

BMH算法

两个点，第一是偏移表的计算，第二是具体去模拟算法的过程。

对比代码看图即可。

后记

属于是寄的比较彻底了😅，虽然基本都是PPT原题吧，但是实际上感觉自己也没咋记住那种，考的雀实烂，我没想到居然考试能这么哈工大hh，其实也是自身原因吧，复习的时候基本就是随性复习，哪里感兴趣就去整哪里，没咋重视ppt的细节实现(＞人＜;)。

但是通过本学期的算法学习，真的收获了很多，有了算法思维的形成，也是非常棒，对，虽然考试是炸了，但是zxr收获的东西却是美妙的，启发性的(当然考试考的好一点就更好了/(ㄒoㄒ)/~~)。

之前我对于算法的一些理解，要么浅薄，要么就是错的，大一的时候，基本对于算法代码是一窍不通，当时思维好像一直没能转换过来，因为以前都没接触过编程，所以有理解障碍，基本就是停留在数学思维，根本不是计算思维。然后这个状态真的一直就卡了很久，对于算法和编程都是略显抗拒。但是这学期开始，我开始克服这种天然的思维抗拒，去试着理解，虽然上课的时候基本也还是错误的思维吧，直到要考试了，zxr开始考试前一个星期复习(maybe 5 days?)，先去刷大量题目，有了机械记忆，然后自己产生很多疑问和很多理解，以及对于问题本质的探究，幸好有mit，极其符合zxr的xp，思路基本都是对口的，然后这才有了正确的认知，虽然可能还是要改进很多，但是基本的原理本质都能窥探到一些了，无奈复习时间真的很短，有些问题还是有疑问的，而且没咋刷题，后续肯定是要解决的。

所以，准确的说，zxr现在才真正的入门了算法，接下来肯定是要持续学习的，原本准备说这个寒假整整6.001来着，现在看来，直接6.006 + 6.046的一部分 + y总其实是比较合适的，其实6.001也是很不错，只是可能不全看了吧，有时间再整整。

So, does it end?

No, just the beginning~