算法设计与分析期末复习
教材：计算机算法设计与分析（第五版） 王晓东著
一 算法复杂性分析
1 时间复杂性T(n)
最坏情况Tmax(n)
最好情况Tmin(n)
平均情况Tavg(n)=∑p(I)T(I)
其中I是问题规模为n的一个实例，p(I)是实例I出现的概率。
2 渐进复杂性 n->∞时，T(n)留下的主项
上界O(g(n))：f(n)<=cg(n)
下界Ω(g(n))：f(n)>=cg(n)
非紧上界o(g(n)): f(n)<cg(n)
非紧下界ω(g(n))：f(n)>cg(n)
紧渐进界θ(g(n)): c1g(n)<=f(n)<=c2g(n) 等价于f(n)与g(n)同阶
3 常见的复杂性函数
常数C<logn<(logn)2<n<nlogn<n2<n3<2n<n!
4 NP问题与NPC问题
5 题目
1-4 金币阵列问题
二 递归与分治
对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归地进行下去，直到问题规模足够小，很容易求出其解为止。将求出的小规模的问题合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
一些递归函数可以用非递归方式定义，如阶乘、斐波那契数列；有一些不可以，如双递归函数Ackerman函数。
附ackerman函数代码，它的增长随m非常快，到m=4时已经非常之大，将超过宇宙原子数量的总和。
int ackerman(int n,int m){
if(n==1&&m==0)return 2;
if(n==0&&m>=0)return 1;
if(m==0&&n>=2)return n+2;
return ackerman(ackerman(n-1,m),m-1);
}
递归函数要有边界条件（退出递归）和递归方程。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。在用分治法设计算法时，最好使子问题的规模大致相同。
题目集
全排列问题 整数划分问题 汉诺塔问题 最大公共子序列问题 分解式的个数
二分搜索 棋盘覆盖 归并排序 快速排序 线性时间选择 最接近点对问题 循环赛日程表
递归与分治题目集
三 贪心
在一些情况下，贪心可以得到最优解。而在其他情况下，贪心也可得到近似最优解。
贪心题目集
四 动态规划
经分解得到的子问题往往不是互相独立的，如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，直接调用，就可以避免大量重复计算，从而得到多项式时间算法。
动态规划题目集
五 回溯
回溯是暴力解法，+剪枝。
回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
在一般情况下用递归函数来实现回溯法。
回溯题目集