题目
2-1
When solving a problem with input sizeby divide and conquer, if at each stage the problem is divided into 8 sub-problems of equal size, and the conquer step takesto form the solution from the sub-solutions, then the overall time complexity is __.(2分)
T(N) = 8*T(N/3) + O(N2logN)
8*f(N/3) = 8*O(N2/9*(logN-log3))
= 8/9*O(N2(logN-log3)) < f(N)
故选1
2-2
To solve a problem with input sizeby divide and conquer algorithm, among the following methods, __ is the worst.(2分)
2*T(N/3) + O(N)
- 2*f(N/3) = 2*O(N/3) = 2/3*O(N) < O(N) => O(N)
2*T(N/3) + O(NlogN)
- 2*f(N/3) = 2*O(N/3 * (logN-log3)) < O(NlogN) =>O(NlogN)
3*T(N/2) + O(N)
- 3/2*O(N) > O(N) => O(Nlog23)
3*T(N/3) + O(NlogN)
- O(NlogN)
故选3
2-3
3-way-mergesort : Suppose instead of dividing in two halves at each step of the mergesort, we divide into three one thirds, sort each part, and finally combine all of them using a three-way-merge. What is the overall time complexity of this algorithm ?(2分)
T(N) = 3*f(N/3) + O(N)
3*f(N/3) = 3*O(N/3) = O(N)
=> T(N) = O(N*log3N)
故选3
2-4
Which one of the following is the lowest upper bound offor the following recursion?(4分)
设m = logn 则 2m = n
T(2m)=2T(2m/2) + m
设G(m) = T(2m) 则 G(m) = 2G(m/2) + m
其中a = 2,b=2,k=1,p=0 =>G(m) = O(mlogm)
由于m=logn 故 T(N) = O(lognloglogn)
0 条评论