资源描述：
《《算法分析与设计》》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《算法分析与设计》一、记得哪些算法复杂性的知识？用自己的话简述。算法复杂性分为时间复杂性和空间复杂性。在一般的应用中，着重考虑时间复杂性。除非在一些内存比较少的嵌入式应用中，才两方面都考虑。而时间复杂性一般只考虑最好、最坏和平均三种情况。最有价值的一般是考虑最坏情况的时间复杂性，因为它是一个算法运行时间的上界。当然，也要考虑平均情况下的时间复杂性，比如快速排序，在最坏情况下的时间复杂度为0（22）,而在平均情况下是O（nlogn）o事实证明，快排是个很好的算法，在很多情况下快拍都能以最快速度完成排序。町以
2、用复杂性的阶描述算法的复杂性。二、算法的时间复杂性分析1、如何根据算法的结构分析算法的时间复杂性？根据算法的基木操作重复执行的次数来衡量算法的时间复朵性。2、分析递归算法的方法，归方程方法和递归树。解递归方程有迭代法（递推）法解递归方程，或套用公式）递归树的方法需利用树的基本概念求树高或树的总结点数。1、若对干某常数。0,有例7[n)=97{nl3)+na=9・尿3,彳〃)=久冷）如叱）必丽刁（丿3log”）n£€(0.】]例：归并排序的递归方程：T(n)=2T(n/2)+cn由于3=2,6=2,10^3
3、=1有1和所有充分大的正整数ri^aftnlb)LTS)=aT(n/by^c
4、nhassolution•ifT00=O(f0;•ifa^h.T(w)a〃log/0：•ifa>b.TS尸o(”W)Master定理式和Master定理递归树的重点就是根据算法执行步骤画图，然后加起来再计算。3、常见算法的时间复杂性，例如快速排序、归并排序、折半查找、最小生成树，多段图。算法时间复杂度快速排序O(nlogn)归并排序O(nlogn)拆半查找O(logn)最小生成树Prim算法：O(nA2);Kruskal算法：O(eloge)多段图O(n+m),n为节点，m为边数三、学习了分治法、动态规划
5、、贪心法、回溯法、分支限界的思考策略、基本原理后，你的收获是什么？是否改变了看问题的角度和思维方式?不同的问题有不同的解法，根据实际问题出发，抓住基木点，分析问题现状,得到数学模型，再根据数学模型求解。四.分治法的基本步骤？学过哪几种分割子问题的方法，各有什么特点？分析时间复杂性的方法。基木步骤：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题合并：将各个了问题的解合并为原问题的解。分割方法：①均匀分割：方法简单，但
6、是可能会遇到极端情况导致效率不高。②随机分割：随机分割可以很好的避免一些极端情况，提高效率。时间复杂性分析：一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。设分解阀值nO=l,且解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为n的问题所需的计算时间，则有：T(n)=kT(n/m)+f(n)五、设计动态规划算法包含哪些关键步骤？动态规划方程的含义?对于给出的实例，如何自底向上求解?
7、关键步骤：(1)分析最优解的性质，并刻画其结构特征。(2)递归的定义最优解。(3)以自底向上或自顶向下的记忆化方式(备忘录法)计算岀最优值(4)根据计算最优值时得到的信息，构造问题的最优解动态规划方程：动态规划方程可以方便了解递归过程，进行自底向上的求解。实例：设P(i,j)是一条从Vi中的结点j到汇点t的最小成本路径，COST(i,j)是这条路的成本。则从Vi屮节点j至肛的最小代价为：cost((i,j)=min{cost(i+l,l)+c(j,l)},1^Vi+1,jVi2411n6C0ST(3,6)
8、=min{6+COST(4,9),5+COST(4,10))=7C0ST(3,7)=min{4+COST(4,9),3+COST(4,10))=5C0ST(3,8)=7C0ST(2,2)=min{4十C0ST(3,6),2+COST(3,7),1+COST(3,8)}=7C0ST(2,3)=9C0ST(2,4)=18C0ST(2,5)=15COST(1,l)=min{9+COST(2,2),7+COST(2,3),3+COST
