Question

求高手帮忙做一套算法分析的题目。做好之后再加100。

一 简要回答下列问题（8道题 40分）
如何选择排序、矩阵相乘、树和图算法的时间复杂性计量单位？
算法有几种基本结构？各种结构的时间复杂度的计算规则？
最坏情况下的时间复杂性和平均情况下的时间复杂性的定义？
为什么选择时间复杂度的渐进性态评价算法？
解释f(n)=O(g(n))的意义。
有效算法和无效算法的划分原则？
用分治法设计算法有什么好处？为什么描述分治算法需要使用递归技术？
归并排序算法和快速排序算法划分子问题和合并子问题的解的方法各是是怎样的？
简述二分检索（折半查找）算法为什么比顺序查找的效率高？
贪心法的核心是什么？
背包问题的目标函数是什么？背包问题贪心算法的最优量度是什么？算法是否获得最优解？ 用贪心算法解0/1背包问题是否可获得最优解？
活动安排、prim算法的贪心策略？
动态规划法的基本步骤？
N皇后、图的着色、哈密顿环问题的解空间、约束函数。
回溯法的基本控制流程中“while k>0 do”的含义。
简述分枝限界方法的基本思想。
带限期作业调度问题、0/1背包问题的分枝限界算法的解空间、上下界函数。

二、算法时间复杂性分析 （2题，16分）
分析包含顺序、选择、循环结构和子过程调用的流程的时间复杂性。
用递归方程分析算法MAXMIN、归并排序、Hanoi塔算法的时间复杂度。（需要递归方程解）

三、算法理解 （20分）
贪心算法的一般流程。
归并排序算法
多段图算法
n后问题递归算法
图的着色非递归形式算法。
子集和数算法

五. 算法设计 （3题 24分）
1、深度优先算法（判断有向图是否存在环等问题）
2、归并排序、回溯法
3、多处理机调度、活动安排、找零钱、装箱问题的贪心算法。

Answer 1

如何选择排序、矩阵相乘、树和图算法的时间复杂性计量单位？
排序：排序的循环次数（或递归次数）。
矩阵相乘：做实数乘法的次数。
树：搜索的次数。
图：同树。
算法有几种基本结构？各种结构的时间复杂度的计算规则？
3种
顺序结构：T(n)=O(c)
选择结构：T(n)=O(c)
循环结构：T(n)=O(n)
最坏情况下的时间复杂性和平均情况下的时间复杂性的定义？
在规模n的全部输入中，可以找寻执行一个算法所需的最大时间资源的量，这个量称为对规模n的输入，算法的最坏情况时间复杂性。
对规模都为n的一些有限输入集，执行算法所需的平均时间资源的量称为平均情况下的时间复杂性。
为什么选择时间复杂度的渐进性态评价算法？
因为在规模较小的时候无法客观体现一个算法的效率。
解释f(n)=O(g(n))的意义。
若f(n)和g(n)是定义在正整数集合上的 两个函数，则f(n)=O(g(n))表示存在正的常数C和n0 ,使得当滑颤n≥n0时满足0≤f(n)≤C*g(n)。
简述之就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。
有效算法和无效算法的划分原则？
区分在于问题是否能够精确求解。
用分治法设计算法有什么好处？为什么描述分治算法需要使用递归技术？
分治法可以将问题分为许规模更小的子问题，这些子问题相互独立且与原问题相同。使用递归技术，虽然一些简单的循环结构替代之，但是复杂的问题，比如二阶递归是无法替代的。
归并排序算法和快速排序算法划分子问题和合并子问题的解的方法各是是怎样的？
归并排序算法：
划分子问题：每次分成2个大小大致相同的子集和
合并子问题：将2个排好序的子数组合并为一个数组
快速排序算法：对输入的子数组a[p:r]
划分子问题：划分为a[p:q-1],a[q]和a[q+1:r]使a[p:q-1]任意元素小于a[q]，a[q+1:r] 任意元素大于a[q]
合并子问题：不需要（因为划分过程就已经排序完成了）
简述二分检索（折半查找）算法为什么比顺序查找的效率高？
对于二分搜索 最坏情况为橡顷O(logn)时间完成
而顺序查找 需要O(n)次比较
显然二分搜索效率高
贪心法的核心是什么？
贪心算法是通过一系列选择得到问题的解，它所作出的选择都是当前状态下的最佳信如败选择。
背包问题的目标函数是什么？背包问题贪心算法的最优量度是什么？算法是否获得最优解？ 用贪心算法解0/1背包问题是否可获得最优解？
Max=∑Vi*Xi (V是价值X取1，0表示装入或不装)
每次选取单位重量价值最高的
不一定是最优解

情况不妙啊 LZ还要继续否。。。
早知发邮件了。。。

Answer 2

看样子纯拿沙莎老师的课程试卷没什么改动呀。。。。。。

同学你这样子让莎莎老师以后都不敢透或并题了，你这是害了中南大学计算机科学与技术专业所有学弟，强烈谴责！

你也伤害沙莎老师了。再次谴衫裤迹责！

Answer 3

现在的学生们越来越聪谈姿碧明了。明天的考试不会很难的，但是题不一定都在这册皮里面，只要你们听了课，好好复习就能过。含举

Answer 4

老师们应该出点偏的题，让他们课本翻不着上网查不到，哈哈~反正我今天刚考完大学最后一门考试

Answer 5

我表示昨晚一个通宵，从分治开始一直看到回溯……幸好只考了一题的分支限界~
压力好大啊~