3T(n/4)+nlogn的增长渐进阶
时间: 2023-06-10 11:07:11 浏览: 59
根据主定理(Master Theorem),对于递归式T(n) = aT(n/b) + f(n),其中a≥1,b>1是常数,f(n)是一个渐进正的函数,则有以下三种情况:
1. 如果f(n) = O(n^k),其中k≤logb(a),则T(n) = Θ(n^logb(a))。
2. 如果f(n) = Θ(n^k log^m n),其中k=logb(a),则T(n) = Θ(n^k log^(m+1) n)。
3. 如果f(n) = Ω(n^k),其中k≥logb(a)>0,并且存在一个常数c<1,使得对于充分大的n有af(n/b)≤cf(n),则T(n) = Θ(f(n))。
对于给定的递归式T(n) = 3T(n/4) + nlogn,我们可以将其表示为a=3,b=4,f(n)=nlogn。因为logb(a)=log4(3)≈0.793,所以我们处于情况3。同时,我们可以计算出af(n/b)=3(n/4 log(n/4))=3/4 (nlogn - nlog4)=3/4 nlogn - 3/4 nlog4。因为3/4<1,且f(n) = Ω(n^k)其中k=logb(a)=log4(3)≈0.793,所以根据主定理,T(n) = Θ(f(n)),也就是T(n) = Θ(nlogn)。因此,递归式T(n) = 3T(n/4) + nlogn的增长渐进阶是O(nlogn)。
相关问题
利用主定理说明以下时间函数的复杂度: T(n) = 9T(n/3) + n ;T(n) = T(2n/3) + 1 ;T(n) = 3T(n/4) + nlogn;T(n)=2T(n/2)+n
根据主定理,对于时间函数 T(n) = 9T(n/3) + n,其中 a = 9,b = 3,d = 1,可以得到 T(n) 的复杂度为 O(nlogb a) = O(nlog3 9)。
对于时间函数 T(n) = T(2n/3) + 1,其中 a = 1,b = 3/2,d = 0,可以得到 T(n) 的复杂度为 O(logb n) = O(log3/2 n)。
对于时间函数 T(n) = 3T(n/4) + nlogn,其中 a = 3,b = 4,d = nlogn,可以得到 T(n) 的复杂度为 O(nlogb a) = O(nlog4 3)。
对于时间函数 T(n) = 2T(n/2) + n,其中 a = 2,b = 2,d = n,可以得到 T(n) 的复杂度为 O(nlogb a) = O(nlog2 2) = O(n)。
利用主定理说明以下时间函数的复杂度: T(n) = 9T(n/3) + n ;T(n) = T(2n/3) + 1 ;T(n) = 3T(n/4) + nlogn;T(n)=2T(n/2)+2
根据主定理,可以得到以下各时间函数的复杂度:
T(n = 9T(n/) + n: 时间复杂度为 O(nlog3(9))
T(n) = T(2n/3) + 1: 时间复杂度为 O(log2/3n)
T(n) = 3T(n/4) + nlogn: 时间复杂度为 O(nlog43)
T(n) = 2T(n/2) + 2: 时间复杂度为 O(n)
注:上述公式中的log均表示以2为底的对数。