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算法思想：

• 第一步，按照元素关键字的最低位数字d₁ 排序，排序之后合并成一个链表
• 第二步，按照元素关键字的次低位数字d₂ 排序，重复第一步的工作，得到的新链表以关键字的最低两位数字排序
• 依次类推，经过第k步，按照元素关键字最高位数字d_k 排序，重复第一步的工作。

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 手动模拟写出基数排序的过程

​ 习题P₈₄ T₁₄：初始链表的内容为：3562,6381,0356,2850,9136,3715,8329,7481，写出用基数排序算法对他们进行排序的过程。

6.3.2 按任意基数进行排序的算法

​ 习题 P₈₅ T₁₅：将基数作为参数，编写一个可以按照任意基数进行排序的算法。

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 用分治法求 A^B

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) ;
}

13 背包问题动态规划法的手动计算(填表)

13.1 背包问题动态规划算法

13.2 例题 6.6

13.3 习题6.8

13.4 习题6.9

14 单源最短路径贪婪法的手动计算

14.1 例题 5.3

14.2 习题 5.3

15 设计特定要求(时间复杂度)的算法