算法设计与分析试é¢?/p>
(中国科学院大学
-
陈玉ç¦?/p>
-2011
秋)
一
.
回答下列问题ï¼?/p>
(
每小é¢?/p>
5
�/p>
)
1.
陈述算法在最坏情况下的时间复杂度和平均时间复杂度ï¼?/p>
这两种评估算法复杂性的方法各自æœ?/p>
什么实际意义?
最坏情况下的时间复杂度称最坏时间复杂度ã€?/p>
一般不特别说明ï¼?/p>
讨论的时间复杂度均是最坏情å†?/p>
下的时间复杂度ã€?/p>
这样做的原因是:
最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界ï¼?/p>
这就保证
了算法的运行时间不会比任何更长ã€?/p>
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下,算法的期望运行时间ã€?/p>
2.
阐述动态规划算法与贪心算法的区别,它们都有那些优势和劣势?
动态规划算法与贪心算法都要求问é¢?/p>
具有最优子结构性质
ï¼?/p>
这是二者的一个共同点ã€?/p>
但是对于å…?/p>
有最优子结构的问题应该选择前者还后者来解决?下面通过两个经典的组合优化问题谈谈动æ€?/p>
规划算法与贪心算法的主要差异
动态规划法与分治法和贪心法类似,它也是将原问题分解为若干个更小的、相似的子问题,
并通过求解子问题产生一个全局最优解。与分治法和贪心法不同之处在于:
â‘?/p>
使用贪心法时ï¼?/p>
当前的选择可能要依赖于已经作出的所有选择,但不依赖于有待于做出的é€?/p>
择和子问题ã€?/p>
因此贪心法是自顶向下
(
即从起点到终ç‚?/p>
)
,一步一步地作出贪心选择。当然,如果
当前的选择可能要依赖于子问题的解时,则难以通过局部的贪心策略达到全局最优解ã€?/p>
â‘?/p>
使用分治法时ï¼?/p>
由原问题分解出的各子问题通常是相互独立的,即不包含公共的子问题,å›?/p>
此一旦递归地求出各子问题的解后ï¼?/p>
便可自下而上地将各子问题的解合并成问题的解ã€?/p>
如果各子
问题不是相互独立的,则分治法要做许多不必要的工作,重复地求解公共的子问题ã€?/p>
â‘?/p>
动态规划允许由
原问题分解出的子问题之间相互依赖
。每一个子问题只求解一次,并将结果
保存起来,避免每次碰到此子问题时都要重复计算
3.
阐述回溯算法与分枝限界算法的共同点和不同点,提高算法效率的关键是什么?