算法分析复习讲解.ppt

1.算法的五个基本特征包括输入、输出、 、能行性和 。 2.算法分析时通常只考虑三种情况下的时间复杂性，实践表明可操作性最好且最有实用价值的是 情况下的时间复杂性。 3.将复杂问题按照某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题进而求解的方法称为 法。 4.利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，这种算法称为 法。 5.动态规划算法的两个基本要素是 和 。 6.在解决最优化问题的求解过程中，采用一种局部最优策略，把问题范围和规模缩小，最后把每一步的结果合并起来得到一个全局最优解，这种算法称为 法。 7. 法在问题的解空间树中，按深度优先策略，从根结点出发有哪些信誉好的足球投注网站解空间树 8. 法在问题的解空间树中，按广度优先策略，从根结点出发有哪些信誉好的足球投注网站解空间树 1、请回答：什么是算法？算法应具有哪些重要特性？ 2、阐述算法与程序的联系与区别。 3、影响一个程序运行时间的因素有哪些？ 4、简述贪心算法的思想策略、算法特点，以及它所具有的两种性质各是什么？ 5、简要说明贪心算法的两个基本要素。 6、请说明回溯法和分支限界法的不同之处。 7、设计一个动态规划算法，通常采用的步骤有哪些？ 渐近时间复杂度 使用O、?、 ?、o等记号表示的算法时间复杂度函数的数量级别，称为算法的渐近时间复杂度 2.2.1 大O记号 定义2-1 设函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数c和n0，使得当n≥n0时，有f(n)≤cg(n)，则称当n充分大时，函数f(n)上有界，且g(n)是它的一个上界。也可以说f(n)的阶不高于g(n)的阶。记做f(n) = O(g(n))，称为大O记号（big Oh notation）。 2.2.2 ?记号 定义2-2 设有函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数 c和n0，使得当n≥n0时，有f(n)≥cg(n)，则称当n充分大时，函数f(n)下有界，且g(n)是它的一个下界。也可以说f(n)的阶不低于g(n)的阶。记做f(n) = ? (g(n))，称为?记号（omega notation）。 2.2.3 ?记号 定义2-3 设有函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在正常数c1，c2和n0，使得当n≥n0时，有c1 g(n)≤f(n)≤c2 g(n)，则记做f(n) = ?(g(n))，称为?记号（Theta notation）。 ?(g(n))代表一类函数，表示所有与g(n)增长阶数相同的函数。 如果一个算法的时间复杂度f(n)= ?(g(n))，说明当n足够大时，该算法的运行时间大约为g(n)的某个常数倍。 证明： (1)f(n)=20n+logn,g(n)=n+log3n 确定函数f(n)和g(n)的渐进关系（用O、 ?、 ?表示） (2)f(n)=n2/logn,g(n)=nlog2n 练习 1、求函数的渐进表达式 （1） 3n2+10n （2） n2/10+2n （3） 21+1/n （4） logn3 （5） 10log3n 2、确定函数f(n)和g(n)的渐进关系（用O、 ?、 ?表示） （1） f(n)=logn2; g(n)=log(n+5) （ ?） （2） f(n)=logn2; g(n)=n1/2 （O） （3） f(n)=n; g(n)=log2n （ O） （4） f(n)=nlogn+n; g(n)=logn （ ?） （5） f(n)=10; g(n)=log10 （ ?） （6） f(n)=log2n; g(n)=logn （ ?） （7） f(n)=2n; g(n)=100n2 （ ?） （8） f(n)=2n; g(n)= 3n （ O） （9）f(n)=20n+logn, g(n)=n+log3n （ O） 贪心法（P120 6-1） 一、背包问题。 n=5,m=11,(p0…p4)=(8,6,15,6,3) (w0…w5)=(2,3,5,2,3), 最优量度标准：优先选择单位重量收益最大的物品放入背包。 (p0/w0, p1/w1, p2/w2, p3/w3,p4/w4)=(4,2,3,3,1) 最优解为：(x0,x1,x2,x3,x4,x5,x6) =(1,2/3,1,1,0) 最大收益为:8+6*2/3+15+6)=33 D[0]=0, S[0]=-1 扩展0