算法导论笔记

Posted on Edited on In Views:
Symbols count in article: 3k Reading time ≈ 3 mins.
《算法导论》笔记

基础知识

==算法是什么？==

graph LR
    A((Input)) --> B[Calculate Sequence]
    B --> C((Output))

排序算法

1、插入排序

对于插入排序，最好的模型是从小到大排手中的扑克牌。

不过我们想象一个牌堆，初始时手中无牌，排序的过程就是抽牌-->比大小-->插入的循环。

反映到逻辑结构为线性的数组里，就是：

  1. 首先选定一端为手中的一张排好序的牌，则其相邻牌到另一端即为从上往下的牌堆；
  2. 从牌堆抽牌，比较的顺序为从中间到端点，依次比较当前牌与手牌；
  3. 未找到位置，则比较到的手牌的位置往中间移动一位；找到位置，则插入该位置；、

先大后小：

1
2
3
4
5
6
7
8
9
10
11
12
int a[10] = {1,3,4,6,8,2,0,9,5,7};
int j = 8;//初始手牌为最末一个，当前牌则位置减一
int i, key;//i为比较用下标，key为当前牌
for(; j >= 0; j--){//从中间到另一端遍历数组
    key = a[j];
    i = j + 1;//比较的位置从当前牌的后一位，即最近的手牌开始
    while(i <= 9 && key > a[i]){//未找到位置，即当前牌比比较的手牌大
        a[i-1] = a[i];//比较的手牌位置移动一
        i = i + 1;//继续比较
    }
    a[i-1] = key;//找到位置，赋值
}

先小后大：

1
2
3
4
5
6
7
8
9
10
11
12
int a[10]={1,3,4,6,8,2,0,9,5,7};
int j = 1;//初始手牌为第一个，当前牌则位置加一
int i, key;//i为比较用下标，key为当前牌
for(; j < 10; j++){//从中间到另一端遍历数组
    key = a[j];
    i = j - 1;//比较的位置从当前牌的前一位，即最近的手牌开始
    while(i >= 0 && key < a[i]){//未找到位置，即当前牌比比较的手牌大
        a[i+1] = a[i];//比较的手牌位置移动一
        i = i - 1;//继续比较
    }
    a[i+1] = key;//找到位置，赋值
}

插入排序的实现，需要注意的是，选定一端为已排序子列A[1, j-1]，从另一子列A[j, n]开始，依次与已排序子列比较，并注意位置的移动。

循环不变式

为达到算法目的的子集，用于证明算法正确性。

类似于数学归纳法，首先初始化需为真，然后过程需要保持真，最后满足终止条件时仍为真。（数学归纳法的归纳步数可为无限）。

2、选择排序

分为已排序子列和未排序子列。

以从小到大为例：

A[0, i]为已排序子列，A[i+1, n-1]为未排序子列；

查询A[i+1, n]中最小值及最小值的位置（即依次取每个值进行比较，初始值为第一个值即其位置）；

最小值与A[i+1]交换位置，直至全部排好序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int a[10]={2,3,4,8,6,9,1,7,5,0};
int i=0;
int j,des;
int MIN;
for(;i<9;i++){				// n
    MIN = a[i];				// n-1
    des = j;				// n-1
    for(j=i;j<10;j++){		// n(n+1)/2
        if(a[j]<MIN){		// n(n+1)/2 - 1
            MIN = a[j];		// n(n+1)/2 - 1
            des = j;		// n(n+1)/2 - 1
        }
    }
    a[des] = a[i];			// n-1
    a[i] = MIN;				// n-1
}

时间复杂度为\(\Theta {(n^2)}\)。

3、归并排序

  • 分解：分解待排序的\(n\)个元素的序列为两个\(\frac n2\)的子序列；
  • 解决：使用归并排序排序两个子序列；
  • 合并：合并两个排好序的子序列为有序序列。

可以看出，归并排序使用了递归，，当未排序的子序列长度为1时，递归开始收束。

递归排序的关键在于合并已排序子序列，由于两个子序列都分别有序，所以合并过程只需依次比较未合并子序列的开头即可，因此合并过程的时间复杂度为\(\Theta {(n)}\)。

合并函数

定义MERGE(A, p, q, r)，A为数组，子数组A[p, q]和A[q+1, r]，p、q、r为下标；函数返回数组A部分排好序的A[p, r]。

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
void MERGE(int *A, int p, int q, int r){
	int n1, n2;
	int i,j,k;
	n1 = q - p + 1;		//获取子数组L长度
	n2 = r - q;			//获取子数组R长度
	int L[n1]={},R[n2]={};
	for(i=0;i<n1;i++) L[i] = A[p+i];	//L[n1]赋值
	for(j=0;j<n2;j++) R[j] = A[q+1+j];	//R[n2]赋值
	i = 0;
	j = 0;
	for(k=p;k<=r;k++){
		if(i!=n1 && j!=n2 && L[i]<=R[j]){	//L、R未排完
			A[k] = L[i];
			i++;
		}else if(i!=n1 && j!=n2 && L[i]>R[j]){
			A[k] = R[j];
			j++;
		}else if(i==n1){	//L排完
			A[k] = R[j];
			j++;
		}else{	//R排完
			A[k] = L[i];
			i++;
		}
	}
}

排序函数

1
2
3
4
5
6
7
8
9
void MERGE_SORT(int *A, int p, int r){
	int q;
	if(p<r){
		q = (p+r)/2;		//二分未排序子列
		MERGE_SORT(A, p, q);	//对两个子列分别进行归并排序
		MERGE_SORT(A, q+1, r);
		MERGE(A, p, q, r);		//合并两个已排序子列
	}
}

分析

对于使用了递归调用的算法，我们使用递归式来研究算法的性能。

递归式分析

  • 设\(T(n)\)为算法求解规模为\(n\)的问题的时间；如果问题规模足够小，即\(n\leq c\)时，求解只需要常量时间\(\Theta {(1)}\)；家假设问题被分成了\(a\)个子问题，每个子问题规模是原问题的\(\frac 1b\)；设分解成子问题所需时间为\(D(n)\)，合并子问题的解为原问题的解所需时间为\(C(n)\)。
  • \(T(n)=\begin{cases} \Theta{(1)} & n\leq c \\ aT(\frac nb)+D(n)+C(n) & Others \end{cases}\)

归并排序算法分析

归并排序的时间递归式为： \[ T(n)=\begin{cases} \Theta{(1)} & n=1 \\ 2T(\frac n2)+\Theta{(n)} & n>1 \end{cases} \] 注意到分解问题采用二分，需要\(\Theta{(1)}\)时间，合并问题需要\(\Theta{(n)}\)时间。

可以知道，归并排序的时间复杂度为\(\Theta{(nlog_2n)}\)，在计算机领域也可写为\(\Theta{(nlg_2n)}\)。

二分查找