资源描述：
《算法分析笔记》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第一章渐进复杂度•函数的渐进性态与渐进表达式：一般来说，当/V单调增加且趋于8时，T"V丿也将单调增加趋于8。•对于T(N),如果存在函数「(N),使得当N-8使有仃(N)・r(N))/"N)-0,那么我们就说77N丿是"N丿当A/f8时的渐进性态。•在数学上，「(N)是T(N)当N-8时的渐进表达式。•例如：3Nz+4N!ogN+7与3N2.第2章递归与分治策略一、什么是分治法？•对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。•将求出的小规模的问题的
2、解合并为一个更大规模的问题的解，自底向上逐步求岀原来问题的解。•分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。二、分治法使用条件•该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质•利用该问题分解出的子问题的解可以合并为该问题的解；•该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。三、排序1、插入排序2、归并排序3、快速排序分治策略求解问题可以分为三步：分解；递归地解子问题；组合。有的问题分解难而组合容易，如—快速排序—,有的问题分解容易而组
3、合难，如—归并排序四、最近点对问题S中的点退化为x轴上的n个点xl,x2fxn。用x轴上的某个点m将S划分为两个集合S1和S2,并且S1和S2含有点的个数相同。递归地在S1和S2上求出最接近点对(pl,p2)和(gl,q2),如果集合S中的最接近点对都在子集S1或S2中，则d=min{(pl,p2)f(ql,q2)}§P为所求，如果集合S中的最接近点对分别在S1和S2中，贝IJ一定是(p3“3),其中，p3是子集S1中的最大值，g3是子集S2中的最小值。第三章动态规划一、算法总体思想•动态规划算法与分治法类似，其基本思想也是将待求解问题分
4、解成若干个子问题•但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。•如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。二、矩阵连乘问题三、最优子结构矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。利
5、用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。证明0/1背包问题具有最优子结构性质即若背包容量为C时，(yl,y2,•••yn)为待选物品为1到n时knap(l,n,c)的最优解，则(y2,•••yn)将是物品1作出选择后的子问题knap⑵n,a)的晶价解当第一个物h做出决策后，有两种状态yl=0,则背包容量没有影响，(y2,•••yn)是kanp(2,n,c)的最优解。yl二1,则背包容量减少wl,价值增长vl,(y2,•••yn)是knap(2,n
6、,c)的最优解。证明：若(z2,••zn)是下述子问题的一个最优解，而(y2,•••yn)不是它的:优解已知：p=max(vlxl+v2x2++vnxn);Wlxl+w2x2+・・+wnxn<=c-wlxl・ynxn;则v2z2+v3z3+・・・・vnzn>y2x2+y3x3+且wlyl+w2v2+….wnvn<=c;Ylyl+v2z2+・vnzn>ylyl+y2y2+ynxn;这说明(yl,z2,•••zn)是所给问题的一个更优解,从而(yl,y2,•••yn)不是原问题的最优解，矛盾。背包问题的递归关系设背包问题的子问题的最优值为m(
7、i,j)，即m(i,j)是背包容量为j,可选择物品为i,i+1,•••,n时的最优值。当选择第i个物品时，m(i,j)=m(i+1,j-wi)+vi如果不选择第i个物品，则m(i,j)二m(i+1,j)。由问题的最优子结构性质，我们可以建立计算m(i,j)的递归式如下：当j>=wi时则有m(i,j)=当jWi)否则m(n,j)=0;四.备忘录方法•备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘
8、录方法为每个解过的子问题建立了备忘录以备需要时査看，避免了相同子问题的重复求解。第四章贪心算法一、什么是贪心算法•贪心法，顾名思义，是一种贪婪的算法，而且是一种每一步都贪婪的算法。•只顾眼前利
