利用主定理说明以下时间函数的复杂度: T(n) = 9T(n/3) + n ;T(n) = T(2n/3) + 1 ;T(n) = 3T(n/4) + nlogn;T(n)=2T(n/2)+2
时间: 2023-06-07 20:08:38 浏览: 139
1. T(n) = 9T(n/3) n:
根据主定理的公式,a=9,b=3,d=1,因为logb(a)>d,所以T(n)的时间复杂度为O(nlog3(9))。
2. T(n) = T(2n/3) 1:
根据主定理的公式,a=1,b=3/2,d=0,因为logb(a)=0<d,所以T(n)的时间复杂度为O(1)。
3. T(n) = 3T(n/4) nlogn:
根据主定理的公式,a=3,b=4,d=nlog4(3),因为logb(a)<d,所以T(n)的时间复杂度为O(nlog4(3))。
4. T(n)=2T(n/2) 2:
根据主定理的公式,a=2,b=2,d=2,因为logb(a)=1=d,所以T(n)的时间复杂度为O(nlogn)。
相关问题
利用主定理说明以下时间函数的复杂度: T(n) = 9T(n/3) + n ;T(n) = T(2n/3) + 1 ;T(n) = 3T(n/4) + nlogn
对于T(n) = 9T(n/3) + n,我们可以使用主定理,其中a = 9,b = 3,d = 1,因为logba = log39 ≈ 2.08 > d,所以时间复杂度为O(nlog39)。
对于T(n) = T(2n/3) + 1,我们可以使用主定理,其中a = 1,b = 3/2,d = 0,因为logba = log31.5 ≈ 0.584 < d,所以时间复杂度为O(n^dlogn) = O(logn)。
对于T(n) = 3T(n/4) + nlogn,我们可以使用主定理,其中a = 3,b = 4,d = 1,因为logba = log43 ≈ 0.793 > d,所以时间复杂度为O(nlog43)。
利用主定理说明以下时间函数的复杂度: T(n) = 9T(n/3) + n ;T(n) = T(2n/3) + 1 ;T(n) = 3T(n/4) + nlogn;T(n)=2T(n/2)+n
答案:对于第一个时间函数,根据主定理,a=9,b=3,d=1,因为log3(9) > 1,所以复杂度为O(nlog3(9))。
对于第二个时间函数,根据主定理,a=1,b=2/3,d=0,因为log(2/3)1 < 0,所以复杂度为O(1)。
对于第三个时间函数,根据主定理,a=3,b=4,d=nlogn,因为log4(3) < nlogn,所以复杂度为O(nlogn)。
对于第四个时间函数,根据主定理,a=2,b=2,d=n,因为log2(2) = 1,所以复杂度为O(nlogn)。
阅读全文