Question

算法设计与分析的题目，求高手啊

证明：如果分治法的合并可以在线性时间内完成，则当子问题的规模之和小于原问题的规模时，算法的时间复杂性可达到O(n)。
这是关于分治法的题

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还要继续否。。。
早知发邮件了。。。

追问

好像有些头绪了，
若f(n)和g(n)是定义在正整数集合上的 两个函数，则f(n)=O(g(n))表示存在正的常数C和n0 ,使得当n≥n0时满足0≤f(n)≤C*g(n)。
这个是不是关键点

Answer 2

上面那个完全是照搬别人的嘛，问题也都不一样的。关键点在于子规模与合并这间的关系