中科院计算机算法_陈玉福_历年试题 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行认真校对，但是难免会有疏漏的地方，但是任然希望（中科院计算机算法_陈玉福_历年试题）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。本文可编辑可修改，假如觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以下为中科院计算机算法_陈玉福_历年试题的全部内容。中国科学院讨论生院课 程 编 号 ：711008Z－1 试 题 专 用 纸课程名称:计算机算法设计与分析任课老师： 陈玉福————-———-————-——---———-—————-——-————-—————————- 姓名 学号 成绩 1. 回答下列问题： (每小题 5 分）1。陈述算法在最坏情况下的时间复杂度和平均时间复杂度；这两种评估算法复杂性的方法各自有什么实际意义？最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长.平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。2. 阐述动态规划算法与贪心算法的区别，它们都有那些优势和劣势？动态规划算法与贪心算法都要求问题具有最优子结构性质，这是二者的一个共同点。但是对于具有最优子结构的问题应该选择前者还后者来解决？下面通过两个经典的组合优化问题谈谈动态规划算法与贪心算法的主要差异3. 动态规划法与分治法和贪心法类似,它也是将原问题分解为若干个更小的、相似的子问题，并通过求解子问题产生一个全局最优解.与分治法和贪心法不同之处在于：① 使用贪心法时,当前的选择可能要依赖于已经作出的所有选择,但不依赖于有待于做出的选择和子问题。因此贪心法是自顶向下(即从起点到终点)，一步一步地作出贪心选择.当然,假如当前的选择可能要依赖于子问题的解时，则难以通过局部的贪心策略达到全局最优解.② 使用分治法时，由原问题分解出的各子问题通常是相互独立的,即不包含公共的子问题，因此一旦递归地求出各子问题的解后，便可自下而上地将各子问题的解合并成问题的解。假如各子问题不是相互独立的,则分治法要做许多不必要的工作，重复地求解...
