课后参考题 答案
1.什么是算法?算法必须满足的五个特性是什么?
算法:一组有穷的规则,规定了解决某一特定类型问题的一系列运算。(有限指令的集合,遵循它可以完成一个特定的任务).
必须满足的五个特性是(遵循以下五条准则): 1.有穷(限)性 2.确定性
3.可(能)行性 4.输入(n≥0) 5.输出(n≥1) 2.对算法进行分析分哪两个阶段?各自完成什么任务(分别得到什么结果)?
对一个算法要作出全面的分析可分成两个阶段进行,即:事前分析和事后测试。
事前分析求出该算法的一个时间界限函数;
事后测试搜集此算法的执行时间和实际占用空间的统计资料。
3.证明:若f1(n)=O(g1(n))并且f2(n)= O(g2(n)),那么f1(n) +f2(n)= O(max{g1(n), g2(n)}
证明:
根据f1(n)=O(g1(n))可知,存在正常数C1,当n≥n0时,使得|f1(n)|≤C1|g1(n)|; 同理,根据f2(n)= O(g2(n))可知,存在正常数C2,当n≥n0时,使得|f2(n)|≤C2|g2(n)| 当n≥n0时,|f1(n)+f2(n)|≤|f1(n)|+|f2(n)|≤C1|g1(n)|+C2|g2(n)| ≤C1|gk(n)|+C2|gk(n)|
≤(C1+C2)|gk(n)|, 其中gk(n)=max{g1(n),g2(n)},k={1,2}
当n≥n0时,取C=(C1+C2),据定义命题得证。
4.如果f1(n)= Θ(g1(n))并且f2(n)= Θ(g2(n)),下列说法是否正确?试说明之。
(a) f1(n) +f2(n)= Θ(g1(n)+ g2(n))
(b) f1(n) +f2(n)= Θ(min{g1(n), g2(n)}) (c) f1(n) +f2(n)= Θ(max{g1(n), g2(n)}) 答:(a)和(c)均正确,(b)错误。
(a)正确可以根据定义直接证得。
(b)错误可举反例。例:f1(n)= 2n,f2(n)=2 n2 下面证明(c)正确性.
根据上题已经证明f1(n)+f2(n)= O(max{g1(n),g2(n)}),下面只需证明f1(n)+f2(n)= Ω(max{g1(n), g2(n)}),即存在正常数C,使得|f1(n)+f2(n)|≥C(max{g1(n), g2(n)})
根据f1(n)= Θ(g1(n))并且f2(n)= Θ(g2(n)) 得到,当n≥n0时,存在正常数C1、C2 、C3、C4
C1|g1(n)|≤|f1(n)|≤C3|g1(n)|
C2|g2(n)|≤|f2(n)|≤C4|g2(n)|
不妨设max{g1(n), g2(n)}= g1(n)
由于|f1(n)+f2(n)|≥||f1(n)|-|f2(n)||≥|C1|g1(n)|-C3|g2(n)||
=C|max{g1(n), g2(n)}|
华中科技大学《算法设计与分析》复习参考题 隐藏>> 算法设计与分析-复习参考题《李大 diao 碉堡了》 1.什么是算法?算法必须满足的五个特性是什么? 算法:一组...
《算法设计与分析》- 复习与习题_工学_高等教育_... 西安邮电大学计算机学院 复习与习题推荐的参考文献(...大学计算机学院 复习与习题(3)计算题 西安邮电大学...
《算法设计与分析》复习题_工学_高等教育_教育专区。填空 1.直接或间接地调用自身的算法称为 递归 。 2.算法的复杂性是 算法效率 的度量,是评价算法优劣的...
算法设计与分析复习题_工学_高等教育_教育专区。算法设计与分析复习题 1 一个算法应有哪些主要特征? 另附资料 2 分治法(Divide and Conquer)与动态规划(Dynamic...
算法设计与分析复习题_IT/计算机_专业资料。算法设计与分析复习题算法设计与分析复习题 1、 一个算法应有哪些主要特征? 又穷性,确定性,可行性,0 个或多个输入...
算法设计与分析复习题目及答案_信息与通信_工程科技_专业资料。一。选择题 1、二分搜索算法是利用( A、分治策略 A )实现的算法。 C、贪心法 A D、回溯法 ...
计算机算法设计与分析期末考试复习题_工学_高等教育_教育专区。1、二分搜索算法是利用( A、分治策略 A )实现的算法。 C、贪心法 A D、回溯法 )。 D、定义...
算法设计与分析复习题_工学_高等教育_教育专区。西南交通大学,尹治本老师教授的《算法分析与设计》课程题库。答案可不供参考,题目可以看一看。...
算法设计与分析复习题_计算机软件及应用_IT/计算机_专业资料。西南交大 算法 代码部分挺多自己写 也整合了以前的资料 看不懂可以找我聊...
《算法设计与分析》- 复习与习题_工学_高等教育_...大学计算机学院 复习与习题(3)计算题 西安邮电大学...【分析】参考教材和 ppt。 西安邮电大学计算机学院 ...
热门文档