发表更新算法导论16 分钟读完 (大约2361个字)

算法导论笔记

第1章

算法介绍

第2章

  • 用扑克牌举例，介绍了一种插入排序
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    void InsertSort(ElemType *A){
    	printf("length:%d\n", length);
    	for(int j = 1; j < MAXSIZE; j++){
    		int i = j - 1;
    		int tmp = A[j];
    		while(tmp < A[i] && i >= 0){
    			A[i + 1] = A[i];
    			i--;
    		}
    		A[i + 1] = tmp;
    	}
    }
  • 简单介绍了时间复杂度的计算
  • 简单介绍了分治法，并举例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void Merge(ElemType *A, int start1, int end1, int start2, int end2){
	int length1 = end1 - start1;
	int length2 = end2 - start2;
	ElemType L[MAXSIZE], R[MAXSIZE];
	int i, j, p1, p2;
	for(j = start1, i = 0; j <= end1; j++, i++){
		L[i] = A[j];
	}
	L[i] = INT_MAX;//--注意跳出循环后i的值 
	for(j = start2, i = 0; j <= end2; j++, i++){
		R[i] = A[j];
	}
	R[i] = INT_MAX;
	for(i = start1, p1 = 0, p2 = 0; i <= end2; i++){
		if(L[p1] <= R[p2]){
			A[i] = L[p1];
			p1++;
		}
		else{
			A[i] = R[p2];
			p2++;
		}
	}
}
1
2
3
4
5
6
7
8
9
void MergeSort(ElemType *A, int start, int end){
	if(end - start == 0) return;//--注意长度为1数组的表达 
	else{
		int mid = (start + end) / 2;
		MergeSort(A, start, mid);
		MergeSort(A, mid + 1, end);
		Merge(A, start, mid, mid + 1, end);
	}
}
  • 分析算法
    T(n) = aT(n/b) + D(n) + C(n)
    分离的子问题T(n/b)，子问题之和aT(n/b)

第3章

  • 时间复杂度记号
    Θ()：包括上下界
    O()：上界，常使用，最坏情况
    Ω()：下界
    o()：强上界，高阶无穷小
    w()：强下界，低阶无穷小

  • floors and ceilings
    ⌈⌉：向上取整
    ⌊⌋：向下取整

  • 指数对数及其他数学表达式
    除对数lgn = log2n外，其余与数学相同。

第4章

  • 最大的子数列问题
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
int* FindMaxCrossing(ElemType *A, int start, int mid, int end){
	int left_sum = -INT_MAX;
	int right_sum = -INT_MAX;
	int sum = 0;
	int fstart, fend;
	int result[3];
	for(int i = mid; i >= start; i--){
		sum += A[i];
		if(left_sum < sum){
			left_sum = sum;
			fstart = i;
		}
	}
	sum = 0;
	for(int i = mid + 1; i <= end; i++){
		sum += A[i];
		if(right_sum < sum){
			right_sum = sum;
			fend = i;
		}
	}
	result[0] = left_sum + right_sum;
	result[1] = fstart;
	result[2] = fend;
	return result;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int* FindMax(ElemType *A, int start, int end) {
	int result[3], LResult[3], RResult[3], CResult[3];
	if(start == end){
		result[0] = A[start];//result[0] : maxMoney
		result[1] = start;//result[1] : startPos
		result[2] = end;//result[2] : endPos
		return result;
	}
	else{
		int mid = (start + end) / 2;
		ArrayTo(LResult, FindMax(A, start, mid), 3);
		ArrayTo(RResult, FindMax(A, mid + 1, end), 3);
		ArrayTo(CResult, FindMaxCrossing(A, start, mid, end), 3);
		if(LResult[0] > RResult[0]) 
			ArrayTo(result, LResult, 3);
		else 
			ArrayTo(result, RResult, 3);
		if(CResult[0] > result[0])
			ArrayTo(result, CResult, 3);
		return result;
	}
}

  • 矩阵乘法简化算法

  • 用代入法和递归树求时间复杂度（中文翻译为递归式）

  • 主方法求时间复杂度
    T(n) = aT(n/b) + f(n)
    主定理：

第5章

概率分析和随机算法

第6章

堆

  • 数组堆的两个属性：length（数组长）、heap-size（实际存放数据长度，堆顶）。
  • 放在数组中储存，可根据下标判断左/右孩子（2i为左，2i+1为右）。
  • 分为max-heap(最大堆)和min-heap(最小堆)，最大堆的每个父母结点的值都大于孩子结点。

基本算法

  • MAX-HEAPIFY
    比较父母结点与孩子结点的大小，并将最大值放在父母结点位置
    时间复杂度O(lgn)
1
2
3
4
5
6
7
8
9
10
11
12
Status MAX_HEAPIFY(Heap &A, int i){
	if(i >= A.heap_size || i < 0) return ERROR;
	int left, right, max;
	left = A.node[i].lchild;
	right = A.node[i].rchild;
	max = A.node[left].data > A.node[right].data ? left : right;
	if(A.node[max].data > A.node[i].data){
		Exchange(A, max, i);
		MAX_HEAPIFY(A, max);
	}
	return OK;
}
  • BUILD-MAX-HEAP
    利用前一算法构造max-heap(最大堆)
    时间复杂度O(n)
    1
    2
    3
    4
    5
    6
    7
    Status BUILD_MAX_HEAP(Heap &A){
    	//A.heap_size = A.length;
    	for(int i = A.length / 2 - 1; i >= 0; i--){
    		MAX_HEAPIFY(A, i);
    	}
    	return OK;
    }
  • HEAPSORT
    可能是利用堆排序，排完后解散堆
    1
    2
    3
    4
    5
    6
    7
    8
    9
    Status HEAP_SORT(Heap &A){
    	BUILD_MAX_HEAP(A);
    	for(int i = A.heap_size - 1; i > 0; i--){
    		Exchange(A, 0, i);
    		A.heap_size--;
    		MAX_HEAPIFY(A, 0);
    	}
    	return OK;
    }
  • HEAP-MAXIUM
    返回堆的最大值
    1
    2
    3
    ElemType HEAP_MAXIUM(Heap A){
    	return A.node[0].data;
    }
    HEAP-EXTRACT-MAX
    取出堆的最大值
    1
    2
    3
    4
    5
    6
    7
    ElemType HEAP_EXTRACT_MAX(Heap &A){
    	ElemType dataMax = HEAP_MAXIUM(A);
    	Exchange(A, 0, A.heap_size - 1);
    	A.heap_size--;
    	MAX_HEAPIFY(A, 0);
    	return dataMax;
    }
  • MAX-HEAP-INSERT
    增加堆中某位置的值
    1
    2
    3
    4
    5
    6
    7
    8
    9
    Status MAX_HEAP_INSERT(Heap &A, int pos, ElemType key){
    	if(key < A.node[pos].data) return ERROR;
    	A.node[pos].data = key;
    	while(pos != 0 && A.node[A.node[pos].parent].data < A.node[pos].data){
    		Exchange(A, A.node[pos].parent , pos);
    		pos = A.node[pos].parent;
    	}
    	return OK;
    }
    HEAP-INCREMENT-KEY
    堆末尾插入新元素
1
2
3
4
5
6
Status HEAP_INCREMENT_KEY(Heap &A, ElemType key){
	if(++A.heap_size > A.length) return ERROR;
	A.node[A.heap_size - 1].data = -INT_MAX;
	MAX_HEAP_INSERT(A, A.heap_size - 1, key);
	return OK;
}

第7章

概述

将要排序的数分割为比A[q]大和比A[q]小的，再分别对A[p,q-1],A[q+1,r]进行分割，直到完成。

特点

期望的时间复杂度为O(nlgn)，最坏情况为O(n)。通常为O(nlgn)。
方法为分治法。

算法

  • QUICKSORT(A, p, r)
    1
    2
    3
    4
    5
    6
    7
    Status QUICKSORT(Array &A, int p, int r){
    	if(p >= r) return OK;
    	int q = PARTITION(A, p, r);
    	QUICKSORT(A, p, q - 1);
    	QUICKSORT(A, q + 1, r);
    	return OK;
    }
  • PARTITION(A, p, r)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int PARTITION(Array &A, int p, int r){
    	int j = p;
    	for(int i = p; i < r; i++){
    		if(A[i] < A[r]){
    			Exchange(A, i, j);
    			j++;
    		}
    	}
    	Exchange(A, j, r);
    	return j;
    }
  • RANDOMIZED_QUICKSORT
    相当于输入足够大的数组？
    1
    2
    3
    4
    5
    6
    7
    Status RANDOMIZED_QUICKSORT(Array &A, int p, int r){
    	if(p >= r) return OK;
    	int q = RANDOMIZED_PARTITION(A, p, r);
    	RANDOMIZED_QUICKSORT(A, p, q - 1);
    	RANDOMIZED_QUICKSORT(A, q + 1, r);
    	return OK;
    }

第8章

比较排序的最短时间:

  • 通过决策树的深度，可以体现算法的时间复杂度的下界。
  • 定理：任何排序算法的最坏情况都需要Ω(nlgn)的时间复杂度。
  • 结论：Heapsort和Mergesort都是渐进最优排序算法。
线性时间算法
  • Counting sort
    概述：
    A中，有n个比x小的数，则将x放置在第n+1个位置。
    特点：
    适用于比较非负整数且数值较小的数。
    k为须比较的数的最大值，则时间复杂度为Θ(k+n)。
    使用该算法时，通常k=O(n)，则时间复杂度为Θ(n)。
    相同取值的数的输出顺序与输入顺序无关。
    代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Array COUNTING_SORT(Array A, int n){
	int k = getMax(A, n);
	Array B = (ElemType*)malloc(k * sizeof(ElemType));
	Array C = (ElemType*)malloc(n * sizeof(ElemType));
	for(int i = 0; i < k; i++){
		B[i] = 0;
	}
	for(i = 0; i < n; i++){
		B[A[i] - 1]++;
	}
	for(i = 1; i < k; i++){
		B[i] += B[i - 1];
	}
	for(i = 0; i < n; i++){
		B[A[i] - 1]--;
		C[B[A[i] - 1]] = A[i];
	}
	return C;
}
  • Radix sort
    概述：
    根据位数d的重要性，从最不重要的一位开始排序，共排序d次。
    特点：
    引理：对于n位数，单位数的最大值为k，若稳定排序需要Θ(k+n)时间，则Radix sort需要Θ(d(k+n))时间。
    引理：对于n位数，单位数的最大值为k，若稳定排序需要Θ(k+n)时间，对于任意正数r≤b，Radix sort需要Θ((b/r)(n+2^r))时间。
    代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void stableSort(Array &A, Array D, int n){
    	for(int i = 0; i < n - 1; i++){
    		for(int j = i; j < n - 1; j++){
    			if(D[j] > D[j + 1]){
    				exchange(A, j, j + 1);
    				exchange(D, j, j + 1);
    			}
    		}
    	}
    }
    1
    2
    3
    4
    5
    6
    7
    Array RADIX_SORT(Array A, int n, int d){
    	for(int i = 1; i <= d; i++){
    		Array D = getSubArray(A, n, i); //第d位的数 
    		stableSort(A, D, n);
    	}
    	return A;
    }
  • Bucket sort
    概述：
    有n个[0,1)之间的数，根据⌊nA[i]⌋将A中各数分配到B中，再对B[i]中各数进行排序。
    特点：
    要排序的各数均在[0,1)之间。
    B可运用链表。
    时间复杂度为Θ(n)。
    代码：
    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
    void BUCKET_SORT(Array &A, int n){
    	bArray B = (Array*)malloc(n * sizeof(Array));
    	for(int i = 0; i < n; i++){
    		B[i] = (ElemType*)malloc((n + 1) * sizeof(ElemType));
    		B[i][0] = 0;//开头存放大小 
    		for(int j = 1; j < n + 1; j++){
    			B[i][j] = -1;
    		}
    	}
    	//将A分配到B中 
    	for(i = 0; i < n; i++){
    		int pos = (int)ceil(n * A[i]) - 1;
    		int j = 1;
    		while(B[pos][j] != -1 && j < n){
    			j++;
    		}
    		B[pos][j] = A[i];
    		B[pos][0]++;
    	}
    	//对B[i]数据排序 
    	for(i = 0; i < n; i++){
    		if(B[i][0] != 0 && B[i][0] != 1){
    			for(int j = 1; j < B[i][0] + 1; j++){
    				for(int k = j; k < B[i][0]; k++){
    					if(B[i][k] > B[i][k + 1]){
    						double tmp = B[i][k];
    						B[i][k] = B[i][k + 1];
    						B[i][k + 1] = tmp;
    					}
    				}
    			}
    		}
    	}
    	//将B中数据重新给A 
    	i = 0; 
    	int j = 0; 
    	int k = 1;
    	while(i < n && j < n){
    		if(B[j][0] != 0){
    			if(B[j][k] != -1 && k < n + 1){
    				A[i] = B[j][k];
    				B[j][k] = -1;
    				B[j][0]--;
    				k++;
    				i++;
    			}
    			else{
    				j++;
    			}
    		}
    		else{
    			j++;
    			k = 1;
    		}
    	}
    }

第9章

找到最小值

时间复杂度：比较n-1次。
方法：常规做法。
代码：略。

同时找到最小值和最大值

时间复杂度：比较3⌊n/2⌋次。
方法：将A分成两两一组，大的跟max比较，小的跟min比较。
代码：

1
2
3
4
5
6
7
8
void comparing(Array &A, int i, int j){
	ElemType tmp;
	if(A[i] > A[j]){
		tmp = A[i];
		A[i] = A[j];
		A[j] = tmp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void getMaxMin(Array A, int n, ElemType &max, ElemType &min){
	if(n % 2){
		max = min = A[0];
		for(int i = 1; i < n - 1; i = i + 2){
			comparing(A, i, i + 1);
			if(A[i] < min) min = A[i];
			if(A[i + 1] > max) max = A[i + 1];
		}
	}
	else{
		comparing(A, 0, 1);
		min = A[0];
		max = A[1];
		for(int i = 2; i < n - 1; i = i + 2){
			comparing(A, i, i + 1);
			if(A[i] < min) min = A[i];
			if(A[i + 1] > max) max = A[i + 1];
		}
	}
}

随机挑选出第i个最小的数

时间复杂度：Θ(n^2)? O(n)?不通过排序来选择，使算法效率较高。
方法：运用随机分割，可得有k-1个数小于A[q]。若k！=i，则递归再次挑选。
代码：

1
2
3
4
5
6
7
8
ElemType RANDOMIZED_SELECT(Array A, int p, int r, int i){
	if(p == r) return A[p];
	int q = RANDOMIZED_PARTITION(A, p, r);
	int k = q - p + 1;
	if(k == i) return A[q];
	else if(i < k) return RANDOMIZED_SELECT(A, p, q - 1, i);
	else return RANDOMIZED_SELECT(A, q + 1, r, i - k);
}

第10章

Stacks

特征
last-in,first-out(LIFO) 先进后出
基本操作

  • STACK-EMPTY

  • PUSH

  • POP

Queue

特征
first-in,first-out(FIFO)先进先出
基本操作

  • STACK-EMPTY

  • ENQUEUE

  • DEQUEUE

Linked lists

基本操作

  • LIST-SEARCH

  • LIST-INSERT

  • LIST-DELETE

静态指针和静态链表

树

第11章

特征

search time:

  • Θ(n), in the worst case
  • O(1), in the average

用数组T[n]存储关键词的位置

算法导论笔记

https://hcye.xyz/2020/09/15/算法导论笔记/

作者

Hyeee

发布于

2020-09-15

更新于

2020-09-15

许可协议

#

最新文章

分类

标签

C#1
C++6
DataBase7
Django1
Java8
JavaScript1
Lombok1
MyBatis1
MySQL2
Python1
Spring4
c++2
git2
maven1
nexo1
计网1

归档

×