算法分析答案

窗体顶端一、填空题1、时间2、增大3、问题的最优解包含其子问题的最优解4、165、设计算法要本着简单方便可操作的原则6、广度优先搜索法最短7、& 0(2n)< O(n ！ )< 0(nn)v!-if !supportLineBreakNewLine-><!-e ndif->9、在绝大多数情况下，划分得更均衡。10、计算时间与最大流值无关，只与流网络的结构相关。二、简答题1、0(n2)2、原因是最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界, 这就保证了算法的运行时间不会比任何更长。为什么一般情况下，讨论的时间复杂度均是最坏情况下的时间复杂度？3、(1) T(n)=0(n) (2) T(n)= O(no.5)(3) T(n)=0(1)4、:=洼门=f(s,v) -f(s -述M=f(s,v) t e s - s=f(S,T)+ £(S,S)=f(S, T)5、证明：举例如：p=7,4,4,w=3,2,2,c=4时，由于73最大，若按题目要求的方 法，只能取第一个，收益是7。而此实例的最大的收益应该是8，取第2， 3个。三、问答题1、贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择， 即贪心选择来达到，这是贪心算法可行的第一个基本要素，也是贪心算法与动态 规划算法的主要区别。2、 (1)开始的时候，所有的节点u,vw V间的流值都为0,即f(u,v)=0。 (2) 在每一次迭代中，我们将流网络G的流量进行增加，方法就是在一个关联的“剩 余网络” Gf中寻找一条“增广路径”。一旦知道Gf中的一条增广路径的边，就 可以很容易辨别出G中的对应的边，我们可以对这些边上的流值进行修改，从而 增加流量(3)重复第2的操作，直到剩余网络中不再存在增广路径为止.3、T( = 7(«-2) + T(2) + =T (尹-4) + 7(2) + 巩挖 一 2) + T + 啓=于饥一 4) 一 2) +C73 + 272)=T(?2- 6) +c(n - 4) +<?(« 一 2) +cn + 3T=T(2') +cA + c6 Hc(n - 2)+ (“ / 2-1)7(2)=巩旳一2)认+ 4打” _42 1 丿4、有许多算法在结构是递归的：为了解决一个给定问题，算法要一次或多次地 调用其自身来解决相关的子问题。这些算法通常采用分治策略：将原问题分成 n个规模较小而结构结原问题相似的子问题。递归地解这些子问题，然后合并其 结果就得到原问题的解。5、概括起来，算法有以下几个特性：1.确定性：算法的每一种运算(包括判 断)必须要有确切的定义，即每一种运算应该执行何种动作必须是相当清楚的、 无二义性的。2.可实现性：此性质是指算法中有待实现的运算都是相当基本的， 每种运算至少在原理上能由人用纸和笔在有限的时间内完成。3.具有数据输入： 一个算法有零个或多个数据输入，它们是在算法开始之前对算法最初赋予的量， 这些输入取自特定的对象集合。4.具有数据输出：一个算法产生一个或多个输 出，它们是同输入有某种特定关系的量。5.有穷性：一个算法总是在执行了有 穷步之后终止。