问答题求证:O(f(n))+O(g(n))=O(max{f(n),g(n)})。
您可能感兴趣的试卷
你可能感兴趣的试题
1.问答题举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品,即只要正在被考虑的物品装得进就装入背包,则此方法不一定能得到最优解(此题说明0/1背包问题与背包问题的不同)。
6.填空题回溯法是指()。
7.填空题所谓最优子结构性质是指()。
8.填空题所谓贪心选择性质是指()。
9.问答题
有11个待安排的活动,它们具有下表所示的开始时间与结束时间,如果以贪心算法求解这些活动的最优安排(即为活动安排问题:在所给的活动集合中选出最大的相容活动子集合),得到的最大相容活动子集合为多少?
10.单项选择题记号Ω的定义正确的是()。
A.O(g(n))={f(n)∣存在正常数c和n0使得对所有n≧n0有:0≦f(n)≦cg(n)}
B.O(g(n))={f(n)∣存在正常数c和n0使得对所有n≧0有:0≦g(n)≦(n)}
C.O(g(n))={f(n)∣对于任何正常数c>0,存在正数和n0>0使得对所有n≧n0有:0≦f(n)<cg(n)}
D.O(g(n))={f(n)∣对于任何正常数c>0,存在正数和n0>0使得对所有n≧n0有:0≦cg(n)<f(n)}
最新试题
简单描述分治法的基本思想。
题型:问答题
通过键盘输入一个高精度的正整数n(n的有效位数≤240),去掉其中任意s个数字后,剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s,寻找一种方案,使得剩下的数字组成的新数最小。 【样例输入】 178543 S=4 【样例输出】 13
题型:问答题
简单描述回溯法基本思想。
题型:问答题
计算机的资源最重要的是()和()资源。因而,算法的复杂性有()和()之分。
题型:填空题
算法的复杂性是()的度量,是评价算法优劣的重要依据。
题型:填空题
已知非齐次递归方程:其中,b、c是常数,g(n)是n的某一个函数。则f(n)的非递归表达式为:现有Hanoi塔问题的递归方程为:,求h(n)的非递归表达式。
题型:问答题
许多可以用贪心算法求解的问题一般具有2个重要的性质:()性质和()性质。
题型:填空题
用贪心算法设计0-1背包问题。要求:说明所使用的算法策略;写出算法实现的主要步骤;分析算法的时间。
题型:问答题
何谓最优子结构性质?
题型:问答题
f(n)= 6×2n+n2,f(n)的渐进性态f(n)=()
题型:填空题