算法复习

考试范围¶

Cp：1-8

考试题型¶

填空：10*2'=20'
选择：5*2'=10'（1、2包括基本概念、重要算法求解过程、复杂性）
算法分析：5*10'=25'（算法过程：具体求解过程，详情参考课后题答疑ppt）
算法设计：2*10'=20'（算法设计->手写代码）

Chapter 1¶

算法概念、重要特性（5个）特性：输入、输出、有穷性、确定性、可行性算法描述方法（4个）自然语言、流程图、程序设计语言、伪代码题型：选择、填空

Chapter 2¶

时间复杂性分析（渐进分析） 1. 非递归：输入规模、基本语句、求累加和 2. 递归：扩展递归（概念+推导）->练题题型：选择、分析

Chapter 3 暴力¶

串匹配：（BF、KMP ）手写流程¶

BF：逐个比对 KMP：next数组，根据next数组进行移动

选择排序、冒泡排序¶

选择：选每次选最值放入当前位置冒泡：相邻比较，大数沉淀，小数上浮

0/1背包¶

背包：向量枚举

最近对、凸包（概念）¶

最近对：枚举两点求距离凸包：枚举两点成线，判断其他各点与线的相互关系题型：填空、分析、设计

Chapter 4 分治¶

基本概念：设计思想（填空） 1. 划分： 2. 求解子问题： 3. 合并：递归思想和编程（填空、选择、分析）基本原理和代码：

快速排序¶

q_sort(int a[],int l,int r){
    if(r>=l)return ;
    int i=l-1,j=r+1,x=q[l+r>>1];
    while(i<j){
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
    }
    q_sort(q,l,j);
    q_sort(q,j+1,r);
}

最大子段和¶

思路： 1. 划分：从中分开\((a_1->a_{n/2})\)\((a_{n/2+1}->a_n)\)得到三个Max 1. left 前半部分的max 2. mid \(a_1->a_n\)跨越两部分的Max 3. right 后半部分的Max 2. 求解子问题：分别求三组 1. 左右部分通过递归求解 2. 中间部分从n/2开始分别向两边延伸，求左边的s1，右边的s2 二者之和即为所求 3. 合并：取三者的最大值为答案

\(max\{left_{max},mid_{max},right_{max}\}\); 算法分析： n=1时，T(n)=1 n>1时，T(n)=2T(n/2)+n（T(n/2)为左右递归求解，n为从中间向两边遍历）

最近对、棋盘覆盖¶

题型：填空、选择、分析、设计

Chapter 5 减治（分治变种）¶

基本概念（设计思想、求解\(a^n\)）（填空、选择）

二叉查找树、选择问题¶

插入排序、堆排序¶

题型：填空、选择

Chapter 6 DP¶

基本概念（多阶段决策、最优性原理、设计思想）（原理+代码+手写流程）

最长递增子序列问题¶

多段图最短路径问题¶

最长公共子序列问题¶

0/1背包问题¶

题型：填空、选择、分析、设计

Chapter 7 贪心¶

基本概念（设计思想）（原理+代码+手写流程）

埃及分数问题¶

最小生成树问题¶

单源最短路径问题Dijkstra¶

（连续）背包问题¶

贪心策略：按照单位重量价格进行排序

多机调度问题¶

贪心策略：按照结束时间进行排序题型：填空、选择、分析、设计

Chapter 8 回溯¶

基本概念（解空间树、设计思想）（原理+代码+手写流程）考点分析：解空间树的画法

图着色问题¶

八皇后问题¶

题型：填空、选择、分析、设计