算法设计与分析总结.doc

《算法设计与分析总结.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一章绪论1、重要特性L输入2.输出3.有穷性4.确定性5.可行性2、描述算法的方法1.自然语言：优点是直观易懂，缺点是容易出现二义性2.流程图：优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言3.程序设计语言：优点是计算机直接运行，缺点是抽象性差4.伪代码：3、递归算法分析1.猜测技术2.扩展递归技术3.通用分治递归推式cn=1r(〃)=«aT(n/b)+cnkn>1。(成")a>hkT(n)=o(nklogl)a=bk0(系)a

2、描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解；关键一一依次处理所有元素。3.2查找问题中的蛮力法3.2.1顺序查找0(n)322串匹配问题BF0(n*m)BMP0(n+m)0j=lnext[j]=vmax｛妇1d…妇。"广即广小…小「｝1elseBM0(n*m)disl(c)=vm-jj=max{/tj=c&1

3、1背包问题3.4.4任务分配问题O(n!)3.5图问题中的蛮力法3.5.1哈密顿回路问题O(n!)3.5.2TSP问题O(n!)3.6几何问题中的蛮力法3.6.1最近对问题OS?)3.6.2凸包问®O(n3)3.7实验项目——串匹配问题第四章分治法4.1分治法的设计思想设计思想：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的

4、解。步骤:(1)划分(2)求解子问题(3)合并4.2排序问题中的分治法4.2.1递归排序O(nlog2n)4.2.2快速排序O(nlog2。)4.3组合问题中的分治法4.3.1最大字段和问题O(nlog2n)4.3.2棋盘覆盖问题4.3.3循环赛日程安排问题4.4几何问题中的分治法4.4.1最近对问题。(nlog2n)4.4.2凸包问题O(nlog2n)4.5实验项目——最近对问题第五章减治法5.1减治法的设计思想原问题的解只存在于其中一•个较小规模的子问题中，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。5.2查找问题中

5、的减治法5.2.1折半查找0(蛔)522二叉查找树O(log2n)5.3排序问题中的减治法5.3.1堆排序0(厨2。)5.3.2选择问题0"og2巾5.4组合问题中的减治法5.4.1淘汰塞冠军问题0(〃5.4.2假币问题5.5实验项目——8枚硬币问题第六章动态规划法6.1动态规划法的设计思想将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的-•个阶段，将子问题的解求解一次并填入表中，汽需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解。步骤：将原始问题分解为相互重叠的子问题，确定动态规划函数；求解子问题，

6、填表；根据表，自底向」:计算出原问题的解。6.2图问题中的动态规划法6.2.1TSP问题dGU')=min{&+d(k,V-{k})}(keV')d伙,{})=%伙壬，)6.2.2多段图的最短路径问题0(n+m)cosr[/J=min(c/?+cosz[jJ)(Zwi.0

7、V(/,j)=V(/-l，7)X：=<6.3.2最长公共子序列问题O(n*m)L[0][0]=Ud[O]=L[O][j]=0(1L[i-][j]3x^yi&L[i][j-]

8、Vj)5=16.4.2近似串匹配问题0i=Qij=0O(i,j)=0,j>0,Pi=弓min(D(z-1,+Z)(i-1,j)+1,D(i