2020-2021-2学期-算法重点
重点总结
- 算法特点、时间复杂度、空间复杂度、平均复杂度
- 算法复杂度三种记号的严格数学定义、用定义求复杂度
- 循环次数统计求复杂度
- 展开法求递推方程、特征根求递推方程
- 快速排序的平均复杂度
- 基数排序
- 动态规划的两个基本要素
- 贪心算法的基本要素
- 分治法与动态规划的异同
- 分治算法复杂度的主定理(定理4.2)
- 简单问题的分治法设计
- 简单问题的二分法设计
- 背包问题动态规划法的手动计算(填表)
- 单源最短路径贪婪法的手动计算
- 设计特定要求(时间复杂度)的算法
各知识点的细化、实例
1 算法特点、时间复杂度、空间复杂度、平均复杂度
1.1 算法特点：
- 有限性，算法在有限步之后必须终止
- 确定性，算法的每个步骤都有精确的定义，要执行的步骤都是清晰的、无歧义的
- 输入，一个算法有0个或多个输入
- 输出，一个算法有一个或多个输出
- 能行性，算法中有待实现的运算都是基本的运算,原则上可以由人用纸和笔在有限的时间内精确的完成
2 算法复杂度三种记号的严格数学定义、用定义求复杂度
2.1 运行时间的上界—— O 记号
2.2 运行时间的下界—— Ω 记号
-
下界的阶越高，评估的精确度越高。
2.3 运行时间的准确界—— θ 记号
2.4 三者的关系
- 如果 f(n) = O(g(n))，且 f(n) = Ω(g(n)) , 则 f(n) = θ (g(n)) 。
- 如果 f(n) = O(g(n)) , 且 g(n) = O(h(n)) ， 则 f(n) = O(h(n)) 。
- 如果 f(n) = Ω(g(n)) , 且 g(n) = Ω(h(n)) ， 则 f(n) = Ω(h(n)) 。
- 如果 f(n) = θ(g(n)) , 且 g(n) = θ(h(n)) ， 则 f(n) = θ(h(n)) 。
3 循环次数统计求复杂度
3.1 洗牌
4 展开法求递推方程、特征根求递推方程
4.1 特征根求递推方程
4.2 递推法求解递归方程
5 快速排序的平均复杂度
5.1 快速排序的平均复杂度为 nlogn
6 基数排序
6.1算法思想：
- 第一步，按照元素关键字的最低位数字d1 排序，排序之后合并成一个链表
- 第二步，按照元素关键字的次低位数字d2 排序，重复第一步的工作，得到的新链表以关键字的最低两位数字排序
- 依次类推，经过第k步，按照元素关键字最高位数字dk 排序，重复第一步的工作。
6.2 算法代码形式：
// 基数排序 输入：存放元素的链表 L，关键字的数字位数 k 输出：按递增顺序排序的链表 L
template <class Type>
void radix_sort(Type* L , int k){
Type *Lhead[10] , *p ;
int i , j ;
for(i = 0 ; i < 10 ;i ++) Lhead[i] = new Type ; // 分配10个链表的头结点
for(i = 0 ; i < k ; i ++) {
for(j = 0 ; j < 10 ; j ++)
Lhead[j]->prior = Lhead[j]->next = Lhead[j] ; // 将10个链表置空
while(L->next != L){
p = del_entry(L) ; // 删去 L 的第一个元素，使 p 指向该元素
j = get_digital(p , i) ; // 从 p 所指的元素关键字取第 i 个数字
add_entry(Lhead[j] , p) ; // 把 p 所指的元素加入链表 Lhead[j] 的表尾
}
for(j = 0 ; j < 10 ; j ++) append(L,Lhead[j]) ; // 将10个链表链接到 L
}
for(i = 0 ; i < 10 ; i ++) delete(Lhead[i]) ; // 释放10个链表的头结点
}
// 取下并删除双循环链表的第一个元素
// 输入：链表的头结点指针 L 输出：被取下第一个元素的链表 L ，以及指向被取下元素的指针
template <class Type>
Type* del_entry(Type *L){
Type *p ;
if(p != L){
p->prior->next = p->next ;
p->next->prior = p->prior ;
}else p = NULL ;
return p ;
}
// 将一个元素 插入双向循环链表的链尾
// 输入：链表的头结点指针 L 输出 ， 插入元素的指针 p ：插入一个元素后的链表 L
template <class Type>
void add_entry(Type *L , Type *p){
p->prior = L->prior ;
p->next = L ;
L->prior->next = p ;
L->prior = p ;
}
// 取 p 所指向元素的关键字的第 i 为数字(最低位为第 0 位)
// 输入：指向某元素的指针 p ，希望去除的关键字的第 i 位数字的位置 i 输出：该元素的关键字的第i为数字
template <class Type>
int get_digital(Type *p , int i){
int key ;
key = p->key ;
if(i != 0) key = key / power(10 , i) ;
return key % 10 ;
}
// 把链表 L1 的所有元素附加到链表 L 的末端
// 输入：指向链表 L1 和 L 的头结点指针 输出：附加了新内容的链表 L
template <class Type>
void append(Type *L , Type *L1){
if(L1->next != L1){
L->prior->next = L1->next ;
L1->next->prior = L->prior ;
L1->prior->next = L ;
L->prior = L1->prior ;
}
}
6.3 实例
6.3.1 手动模拟写出基数排序的过程
习题P84 T14：初始链表的内容为：3562,6381,0356,2850,9136,3715,8329,7481，写出用基数排序算法对他们进行排序的过程。
6.3.2 按任意基数进行排序的算法
习题 P85 T15：将基数作为参数，编写一个可以按照任意基数进行排序的算法。
7 动态规划的两个基本要素
- 最优子结构
- 重叠子问题
8 贪心算法的基本要素
- 最优子结构
- 贪婪策略(贪婪选择性质)
9 分治法与动态规划的异同
- 相同点
- 二者都要求原问题具有最优子结构性质。
- 都是将原问题分而治之，分解成若干个规模较小(小到很容易解决的程序)的子问题。然后将子问题的解合并，形成原问题的解
- 不同点
- 分治法将分解后的子问题看成相互独立的。动态规划将问题分解为相互间有联系，有重叠部分的子问题
- 分治法通常利用递归求解。动态规划通常利用迭代法自底向上求解，但也能用具有记忆功能的递归法自顶向下求解。
- 分治法解决的问题不一定是最优化问题，而动态规划解决的问题一定是最优化问题。
10 分治算法复杂度的主定理(定理4.2)
11 简单问题的分治法设计
11.1 用分治法重新设计二叉搜索算法
template <class Type>
int binarySearch(Type A[] , int low , int high , Type x){
int mid = (low + high) / 2 ;
if(A[mid] == x) return mid ;
else if (A[mid] > x) return binarySearch(A,mid+1 ,high,x) ;
else return binarySearch(A,low,mid-1,x) ;
}
11.2 用分治法求 AB
typedef long long ll ;
// 用分治法 求 A 的 B 次方
ll myPow(ll a , ll b){
if(b == 1) return a ;
else {
ll temp = myPow(a , b / 2) ;
if(b % 2) return temp * temp * a ;
else return temp * temp ;
}
}
// 用分治法 求 A 的 B 次方 对 C 取余的结果
ll myPowModC(ll a , ll b , ll c){
if(b == 1) return a % c ;
else {
ll temp = myPowModC(a , b / 2 , c) ;
if(b % 2) return temp * temp * a % c ;
else return temp * temp % c ;
}
}
11.3 分治法求二叉树的高度
int TreeDepth(Node * root){
if(!root) return 0 ;
int leftDepth = TreeDepth(root->left) ;
int rightDepth = TreeDepth(root->right) ;
return max(leftDepth , rightDepth) + 1 ;
}
11.4 称硬币的次数
/*
在n（n>=3)枚硬币中有一枚重量不合格的硬币（重量过轻或过重），如果只有一架天平可以用来称重且称重的硬币数没有限制，设计一个算法找出这枚不合格的硬币，使得称重的次数最少？给出算法的伪码描述。如果每称1次就作为1次基本运算，分析算法最坏情况下的时间复杂度！（8分）
*/
// A 是 n 个的硬币的集合
int Coin(A, n) {
if n 等于 1 then return 0 ;
if n 等于 2 then return 1 ;
k = n / 3 ; // 向下取整
将 A 中的硬币分为三部分，X , Y , Z ,且 X 和 Y 中的硬币数为 k , Z 中的硬币数为 n - 2k ;
if W(X) != W(Y) { // W(X) , W(Y) 表示 X，Y 的重量
A 集合赋值为 X 和 Y 集合的并集 ;
return Coin(A , 2k) + 1 ;
}else{
A 集合赋值为 Z 集合 ;
return Coin(A , n -2k) + 1;
}
}
/*
最坏情况下的时间复杂度为 O(logn)
递推方程为 f(n) = f(2n/3) +O(1) ; f(1) = 0 ; f(2) = 1 ;
*/
11.5 求严格第二大的分治算法
12 简单问题的二分法设计
// n 个互不相等的整数，按递增顺序存放于数组A，若存在一个下标 0<=i<n,使A[i]=i,设计一个O(logn)算法找到i
int Search(int a[], int left , int right){
mid = (l + r) / 2; ;
if(A[mid] == mid) return mid ;
else if(A[mid] > mid) return Search(a , left , mid - 1) ;
else return Search(a , mid + 1 , high) ;
}