算法复习总结

《算法复习总结》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、注：有些问题自己不是很清楚，所以答案不一定准确每章老师提到的具体例子，我没有整理答案，自己看课件,希望有同学可以整理下第一章1、什么是算法？它的特点是什么？算法与程序设计联系与区别？答：算法是指解决问题的方法或过程。算法满足以下性质：输入：有零个或多个外部量作为算法的输入；输出：算法产生至少一个量作为输出；确定性:组成算法的每条指令是清晰的、无歧义的；有限性：算法中每条指令的执行次数有限，执行囹条指令的时间也有限。清晰•无歧义零个或多个确定性确定性外部量输入F1输出1算•运AT—输入F1输出1程•T—至少一个量有限性每条指令：执行次数有限，执1行时问有I®▼有限性程序与算法不

2、同。程序是算法用某种程序设计语言的具体体现。可以不满足冇限性。2、算法设计的一般过程是什么？答：根据问题确定数学模型；明确目的、条件与约束关系；设计求解步骤；结果评估与分析。3、算法复杂性的一般概念（定义、组成。。。0的计算）答：算法复杂性是指算法运行时所需要的计算机资源的暈，所需资源越多，该算法的复杂性越高。对于任意给定的问题，设计出复杂性尽可能低的算法是在设计算法时追求的重要目标。当给定问题有多种算法时，选择其中的最低者是选用算法吋遵循的规则。算法复杂性分为：时间复杂性——需耍时间资源的量空间复杂性——需要空间资源的量第二章分治法的基本思想，递归的概念。分治法的基本思想：

3、将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立并R与原问题相同。通过递归地求解这些了问题，然后再将各个了问题的解合并，就可以实现对原问题的求解。递归算法——总接或间接调用自身的算法。递归函——数用函数自身给出定义的函数。优点：使用递归技术可以使函数的定义和算法的描述简洁易懂。2、二分搜索。问题描述：给定己经排好序的n个元索alO:n-l],现在要从这n个元索屮找岀一个特定的元素XO解决方案：方案1：逐个比较——算法复杂度为0(n)方案2：利用元素间的次序关系，采用分治策略，可在最坏情况下用O(k)gn)时间完成任务。3、快速排序线性时间选择第三章1、动态规

4、划的基本思想其基木思想与分治算法的思想类似——分而治Z,即将待求解问题分解为若干了问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法的不同之处：分解后的子问题往往不互相独立；采用记录表的方法来保存所有已解决问题的答案。动态规划算法的设计步骤1.找出最优解的性质，并刻画其结构特征；2.递归地定义最优值；3.以自底向上的方式计算出最优值；4.根据计算最优值时得到的信息，构造故优解。3、可用动态规划算法求解的问题所具有的一般特征最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。可用动态规划算法求解的重要线索举例：在矩阵连乘中，A[l:n]

5、的最优计算次序所包含的计算矩阵了链A[l:k]和A[k+l:n]的次序也是最优的。子问题重叠性质：用递归算法子顶向下求解问题时，每次产生的子问题Z间存在重叠现彖。对每个了问题只求解一次，并将结果保存在一个表屮，当再次遇到该了问题时，只是简单查看即可。通常不同子问题个数随问题的大小呈多项式增长，因此用动态规划算法通常只需要多项式时间可以获得较高的求解效率4、备忘录方法(同动态规划算法相比)备忘录方法是动态规划算法的变形，采用表格保存已经解决的子问题答案，下次需要时查看即可。与动态规划算法的不同之处：动态规划算法：自底向上递归求解备忘录方法：口顶向卜-递归求解其控制结构与直接递归

6、方法的控制结构相同，但备忘录方法为每个求解过的子问题建立了备忘录以备需要时查看最长公共子序列第四早1、贪心算法的基本思想和特点：仅依据当前状态，做出最好选择（即局部最优选择），然后再取解做出这个选择后产生的和应子问题。选择町以依赖于以往的选择，但不依赖于将来的选择只完成基于贪心策略所选择的问题空间分枝上的了问题求解不回溯自顶向下求解3、可用贪心算法求解问题所具有的性质（最优子结构性质&贪心选择性质）最优子结构性质：当一个问题的最优解包含其了问题的最优解时，称该问题具有最优了结构性质。是可以采用动态规划算法或贪心算法的关键特征——动态规划算法和贪心算法的共同点贪心选择性质：所求

7、问题的整体最优解町以通过一系列局部最优的选择（即贪心选择）來达到是贪心算法的一个基本要索最优装载问题、哈夫曼编码第五章1、回溯法的基本思想在确定解空间的纽织结构后，回溯法从开始结点（根结点）出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为新的活结点，并成为扩展结点。如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）到最近的活结点处，并使该结点成为当前的扩展结点。