利用主定理说明以下时间函数的复杂度: T(n) = 9T(n/3) + n ;T(n) = T(2n/3) + 1 ;T(n) = 3T(n/4) + nlogn
时间: 2023-06-05 18:08:20 浏览: 101
第二章 算法时间复杂度
对于第一个时间函数 T(n) = 9T(n/3) + n,我们可以使用主定理来判断其时间复杂度。其中,a = 9,b = 3,f(n) = n。根据主定理,这个时间函数的复杂度为 O(nlogb(a)) = O(nlog3(9)),即 O(n2.177)。
对于第二个时间函数 T(n) = T(2n/3) + 1,同样可以使用主定理来判断其时间复杂度。其中,a = 1,b = 3/2,f(n) = 1。根据主定理,这个时间函数的复杂度为 O(logb(a)) = O(log3/2(1)),即 O(0),也就是常量时间复杂度。
对于第三个时间函数 T(n) = 3T(n/4) + nlogn,同样可以使用主定理来判断其时间复杂度。其中,a = 3,b = 4,f(n) = nlogn。根据主定理,这个时间函数的复杂度为 O(nlogb(a)) = O(nlog4(3)),即 O(n1.26logn)。
阅读全文