算法期末考试复习笔记

发表于 更新于 分类于 阅读次数： 本文字数： 11k 阅读时长 ≈ 10 分钟
这个真的只是期末笔记，只记了老师说的重点，其他数据结构预算法请关注后续更新的算法碎碎念系列

1. 二分搜索

二分搜索的核心思想是把一个有序数组分为两部分，然后判断值在哪一部分，然后再在那一部分中进行二分搜索，直到找到目标值。

代码：循环版

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
#include<iostream>

using namespace std;

int binary_search(int arr[], int x, int n);

int main(void){
    int arr[9] = {1,2,3,4,5,6,7,8,9};
    int x = 5;
    int n = 9;
    int pos = binary_search(arr, x, n);
    cout << pos << endl;
}

int binary_search(int arr[], int x, int n){
    // arr: 数组
    // x: 目标值
    // n: 数组长度
    // return: 目标值的位置索引
    int left = 0;
    int right = n-1;
    int mid = 0;
    while(left < right){
        mid = (int)((left+right)/2)
        if (arr[mid] == x) return mid; //找到并返回
        if (arr[mid] > x){
            right = mid+1;
        } // x在arr的左边
        if (arr[mid] < x){
            left = mid-1;
        } //x在arr右边
    }
    return -1; //未找到目标值
}

代码：递归版

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
#include<iostream>

using namespace std;

int recursive_binary_search(int arr[], int left, int right, int x);

int main(void){
    int arr[9] = {1,2,3,4,5,6,7,8,9};
    int x = 5;
    int n = 9;
    int pos = binary_search(arr, x, n);
    cout << pos << endl;
}

int recursive_binary_search(int arr[], int left, int right, int x){
    // arr: 数组
    // left: 数组（子数组）开始索引
    // right: 数组（子数组）结束索引
    // x: 目标值
    // return: 目标值在原数组中的索引
    int mid = (int)((left+right)/2);
    if (left > right) return -1; //参数错误
    if (arr[mid] == x) return mid; //找到并返回
    if (arr[mid] > x){ // 左边
        recursive_binary_search(arr, left, mid-1, x);
    }
    if (arr[mid] < x){ // 右边
        recursive_binary_search(arr, right, mid+1, x);
    }
}

2. 排序/时间复杂度

2.1 合并排序

合并排序的步骤有：

  1. 分解(Divide)：将原数组通过二分法分为最小的单位数组；
  2. 解决(Conquer)：用合并排序法对两个子序列递归地求解排序；
  3. 合并(Combine)：合并两个已排序的子序列以得到排序结果。
分解过程
合并过程

说这么多不如直接看代码

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>

using namespace std;

void Merge_sort(int arr[], int left, int right);
void Merge(int arr[], int left, int mid, int right);

int main(void){
    int arr[12] = {3,4,1,6,1,3,5,8,12,5,5,12};
    for(int i = 0; i < 12; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
    Merge_sort(arr, 0, 11);
    for (int i = 0; i < 12; i++){
        cout << arr[i] << " " ;
    }
}

void Merge_sort(int arr[], int left, int right){
    // arr: 数组
    // left: 数组（子数组）开始索引
    // right: 数组（子数组）结束索引
    if (left < right){
        int mid;
        mid = (int)((left+right)/2);
        Merge_sort(arr, left, mid); //往左边二分
        Merge_sort(arr, mid+1, right); //往右边二分
        Merge(arr, left, mid, right);
    }

}

void Merge(int arr[], int left, int mid, int right){
    int* B = new int[right - left + 1]; //创建一个辅助数组
    int i = left;
    int j = mid + 1;
    int k = 0;

    //比较操作
    while(i <=  mid && j <= right){
        if (arr[i] <= arr[j]){
            B[k++] = arr[i++];
        }
        else{
            B[k++] = arr[j++];
        }
    }

    //处理剩余元素
    while (i <= mid){
        B[k++] = arr[i++];
    }
    while (j <= right){
        B[k++] = arr[j++];
    }

    //把排好序的数组赋值给arr
    for (i = left, k = 0; i <= right; i++){
        arr[i] = B[k++];
    }

    delete[] B;
}

2.2 时间复杂度

简而言之，计算时间复杂度就是计算代码执行次数的最高次项。考试要求的是给出伪代码计算时间复杂度。

以合并排序为例

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
MERGE(A,p,q,r)
    n1=q-p+1;
    n2=r-q;
    create new arrays L[n1+1] and R[n2+1]
    for i=0 to n1-1
        L[i]=A[p+i]
    for j=0 to n2-1
        R[j]=A[q+1+j]
    L[n1]=99999 //无穷大
    R[n2]=99999
    i=j=0
    for k=p to r
        if(L[i]<=R[j])
            A[k]=L[i]
            i=i+1
        else
            A[k]=R[j]
            j=j+1

MERGE_SORT(A,p,r)
    if p<r
        q=floor((p+r)/2)
        MERGE_SORT(A,p,q)
        MERGE_SORT(A,q+1,r)
        MERGE(A,p,q,r)

函数MERGE的时间复杂度是，因为函数体内部除了三个单层for循环之外没有其他循环了。函数MERGE_SORT的时间复杂度是，的来源是二分法的结果。假如数组长度为，每次分割为长度的数组，一共就要分次，每一次调用MERGE_SORT都有一次MERGE的操作，左右一共次，因此最后为

再比如插入排序的伪代码，因为for循环中套了一个while循环，复杂度上限为，下限为，当数组为逆序时达到上限，顺序时达到下限。

1
2
3
4
5
6
7
for j=2 to A.length
    key=A[j]
    i=j-1;
    while i>0 and A[i]>key
        A[i+1]=A[i]
        i=i-1
    A[i+1]=key

考试复杂度多半从各大排序算法中出题，背一背这张表应该会有用。一个准则就是，一看就很简单能快速算出来的，多半是或者（但排序很少有的），想了半天没想出来的，猜一个概率会比较大。考试伪代码多半从排序算法里出，背一背这张表应该比较有用

3. 动态规划

3.1 概念

动态规划（Dynamic Programming, DP）的基本思想是将待求问题分解为若干子问题，每个子问题不是相互独立的，用分治法求解时有些子问题会被重复计算很多次。DP则采用一个数组的形式储存已经计算过的子问题，在接下来再次遇到该问题时直接查表解决。

DP与分治法的异同

相同点 不同点
DP与分治法都是将目标问题分解为若干子问题，先求解子问题，然后从子问题中求解原问题 DP分解出来的子问题往往不是独立的，如果用分治法求解，则很多子问题会被重复计算

3.2 矩阵连乘加括号问题

直接看例子

6个矩阵连乘，首先应将每个矩阵维度表示出来，由于每个矩阵相乘的时候，左边矩阵的列与右边矩阵的行“抵消掉了”，但第一个矩阵的行列维度都需要保存，所以6个矩阵用7个值就能表示出来。

考试请牢记，第两个矩阵之间的计算量公式为

其中的位置有种可能。有了这个公式，就可以计算出乘法代价表。

如图所示，从矩阵主对角线开始计算，主对角线元素全为0，因为只有一个矩阵，没有乘法。次对角线为相邻两个矩阵相乘的代价，直接计算即可。其余的对角线则需要按照上面提到的公式计算。例如

显然，其余计算同理。图中表示的是最优加括号的位置，比如取的是值7875，所以括号位置应该在第1个矩阵后面,也就是，再把结果填入表中，此时。

如何从表中得到最后6个矩阵加括号的结果呢？

从开始，第一个右括号应该加在的后面，所以应该是。此时连乘被分为了前三个和后三个矩阵连乘两个部分，对于前三个矩阵上面已经说明过应该是，对于后三个矩阵，只需要查询表中的值，这里，所以括号应该加载第五个矩阵后面，也就是。因此这个矩阵连乘代价最小的括号加法应该为

为了美观，整理一下就有

4. 遗传算法

遗传算法只考概念和流程

遗传算法是一种基于自然群体遗传进化机制的自适应全局优化概率搜索算法。

遗传算法有三个关键步骤：

  • 选择

  • 交叉

  • 变异

遗传算法的基本机理：适应度函数。

适应度函数决定了染色体的优劣程度，对于优化问题，适应度函数就是目标函数。

4.1 选择

选择也称赋值操作，根据个体的适应度函数值度量决定该解是否可以遗传到下一代。

主要思想：适应度值较大的染色体有较大的选择（复制）机会

为第个染色体的适应度值。 为种群中所有染色体适应度值之和。

P.S. 个人感觉这里用softmax感觉会更合理

4.2 交叉

将被选择出来的两个个体作为父母个体，将二者部分码值进行交换，这个交换要求产生一个随机数，确定交叉位置。

4.3 变异

随即改变数码串上某个位置的数字

5. 粒子群算法

5.1 PSO的基本思想

每个寻优的问题解称为“粒子”。所有粒子都在一个D维空间进行搜索。所有的粒子都由一个fitness function 确定适应值以判断目前的位置好坏。每一个粒子必须赋予记忆功能，能记住所搜寻到的最佳位置。每一个粒子还有一个速度以决定飞行的距离和方向。这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。

5.2 PSO公式

假设D维空间中有N个粒子，每个粒子有如下参数

  • 粒子位置：，将带入适应度函数求适应值；

  • 例子速度：；

  • 粒子个体经历过的最好位置：

  • 种群经历过的最好位置：

通常，位置和速度都有他们自己的变化范围，若超出了边界值，则该维的速度或位置会被限制维该维最大速度或边界位置。

PSO的核心公式：粒子的第维速度更新公式，实际上是一个递推公式（要求背）

参数解释：

参数 含义
第次迭代粒子飞行速度矢量的第维分量
第次迭代粒子飞行位置矢量的第维分量
加速度常数，调节学习最大步长
两个随即常数，取值范围，增加搜索随机性
惯性权重，非负数，即对前一个状态的依赖程度

理解记忆：PSO速度更新公式有三部分

  1. 递推部分：粒子上一个状态的速度加权

  2. 认知部分：当前粒子自身的思考，可理解为粒子当前位置与自己最好位置之间的距离

  3. 社会部分：可理解为粒子当前位置与群体最好位置之间的距离。

5.3 PSO的参数影响

参数 影响
失去对粒子本身速度的记忆
“只有社会，没有自己”，所有位置更新取决于群体位置，容易陷入局部最优无法跳出
“只有自己，没有社会”，所有位置更新取决于自己位置，没有信息共享，导致算法收敛速度变慢

5.4 全局PSO与局部PSO

全局PSO是指每次更新都使用一个群体内所有粒子的位置信息，局部PSO是指只将群体中的部分个体作为粒子的邻域。类似于Batch SGD和mini-Batch SGD的关系。

二者优缺点： 全局收敛快，但容易陷入局部最优

局部收敛慢，但很难陷入局部最优

5.5 粒子群算法流程

  1. 在初始化范围内，对粒子群进行随机初始化，包括随机位置和速度

  2. 计算每个粒子的适应值

  3. 更新粒子个体的历史最优位置

  4. 更新粒子群体的离职最有位置

  5. 更新粒子的速度和位置，公式如5.2所示

  6. 若未达到终止条件，则跳转第二步

6. 决策树

详情见我写的另一篇笔记，这里只针对考点做总结。

6.1 信息增益

要算信息增益需要先算条件熵

把用贝叶斯公式展开就有

信息增益计算为信息熵减去条件熵。

直接看例子

下图是西瓜数据集，考试也从这个里面出题

最终目的是要区分好瓜坏瓜，所以随即变量好瓜坏瓜，正例有8个反例有9个，则根节点信息熵就可以计算了，注意这里底数为2

要计算信息增益则还需要计算每个属性的条件熵，以色泽为例，色泽为青绿的瓜有6个，其中好瓜3个，则令色泽青绿为

这里是条件熵的原因是分母6并不是整体数据集的数量17，而是指定了“色泽”条件下的数量。

同理可得色泽乌黑()，色泽浅白()的信息熵为

根据信息增益定义式有

6.2 预剪枝与后剪枝

剪枝(pruning)的目的是为了避免决策树模型过拟合。

  1. 预剪枝：指在构造决策树的过程中，先对每个节点在划分前进行估计，若当前的节点划分不能带来决策树模型的泛化能力提升，则不对当前节点进行划分并且将当前节点标记为叶节点。

  2. 后剪枝：指先把决策树构造完毕，然后自底向上地对非叶节点进行考察，若将该节点对应的子树换位叶节点能带来泛化性能地提升，则把该子树替换为叶节点。

7. 聚类

聚类只考K-means聚类

K-means聚类的度量指标是L2距离

K-means聚类的基本步骤为：

  1. 随机选择个样本作为初始均值向量

  2. 计算每个样本与均值向量的L2距离

  3. 根据距离将划分给距离均值向量最近的簇

  4. 划分好之后对每个簇内求平均，重新计算新的均值向量

直接看例子

假定聚类数，则有簇。开始随机选取三个样本做为初始均值向量，则

考察样本，与三个均值向量的L2距离分别为，因此被分到。同理对其他样本也进行求距离-划分的操作。

然后对的所有向量分别求均值（对每个维度都要求），得到更新哈偶的均值向量（聚类中心）

如此循环往复，直到终止条件。

8. 差分进化法

差分进化法与遗传算法有相似的地方，它的基本思想是用当前种群个体的差异来重组得到中间种群，然后应用子代个体与父代个体竞争来获得新一代种群。差分进化法要考公式

8.1 算法流程

差分进化法包含了三个基本操作：变异，交叉和选择，除此之外还有一个初始化操作。

8.1.1 初始化

在维空间上随机产生个个体，具体方法如下

的含义是第代中第个个体的第维向量数值，分别代表生成个体数值的上下限，这个公示的记忆可以类比一下算术编码，都是：下限+取值范围缩放因子。

8.1.2 变异

变异操作是指生成变异向量，为后面交叉和选择操作做准备。

变异的方法为从种群中随机选取三个个体，，且有，也就是说这三个向量不能都是同一个向量，然后用下式计算变异向量

其中为缩放因子。这个式子的就是用第一个向量加上其余两个向量之差的放缩，实际上是这三个向量的线性组合。

由于差分进化算法可以使用不同的差分策略（上述只是其中一种），通常用来表示策略及其参数。其中代表参与变异的向量，表示参加差分变异的向量数量，表示交叉的模式，如二项式交叉，指数交叉等。

例如：就代表随机选择一个向量，用二项式交叉方式。

8.1.3 交叉

交叉是指以一定概率将替换为变异向量，具体用下式实现

其中为交叉概率，这个式子意思就是，如果随机数小于交叉概率，则向量的值就被替换为，反之则保留原有的值。则保证了至少有一个分量是可以替换对应分量的。

结合这张图可以更好理解

8.1.4 选择

选择则是根据适应度函数来选择下一代应该保留原有的向量还是经过变异和交叉过后的向量。其中称为试验个体(trial vector)，称为父向量(parent vector)