(1)Time for merge-sort can be modeled as the recursion T(n)=2T(n/2)+cn
that has solution theta(nlogn).And balance recursion achieves the best result.
Thus the lower bound to sorting problem is Omega(nlogn).
这个叙述错在哪呢?
Merge-sort的best/average/worst case 都是O(nlogn)没错
所以是因为是theta的关系吗?
(2)
long f (long n){
if (n<1) return 0;
if (n<3) return 1;
return f(n-1)+f(n-2);
}
The number of recursive calls grows exponentially with n
这句话的意思是 O(2^n)对吗?
这和费氏数列的时间复杂度应该是一样的
(3)
6(n^3)/(logn+1)的时间复杂度为什么是n^3次呢?
logn跟n^3比太小可以忽略吗??
希望有人能给个指点谢谢!!