利用主定理说明以下时间函数的复杂度: T(n) = 9T(n/3) + n ;T(n) = T(2n/3) + 1 ;T(n) = 3T(n/4) + nlogn
时间: 2023-06-05 16:08:39 浏览: 28
对于第一个时间函数,根据主定理,a=9, b=3, d=0,因为log3(9) > 0,所以复杂度为O(n^2.81)。
对于第二个时间函数,根据主定理,a=1, b=3/2, d=0,因为log3/2(1) = 0,所以复杂度为O(log n)。
对于第三个时间函数,根据主定理,a=3, b=4, d=1,因为log4(3) < 1,所以复杂度为O(n^log4(3)),即约为O(n^0.79)。
相关问题
利用主定理说明以下时间函数的复杂度: 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)。
用主定理求解以下两个递归方程, 1. T(n)=9T(n/3)+5n2 2. T(n)=4T(n/5)+7n
1. 根据主定理,对于递归形式 T(n) = aT(n/b) + f(n),其中a≥1,b>1,f(n)是一个渐进正函数,可得到以下结果:
- 如果 f(n) = O(n^logb a - ε),其中 ε > 0,则T(n) = Θ(n^logb a)。
- 如果 f(n) = Θ(n^logb a logk n),其中 k ≥ 0,则 T(n) = Θ(n^logb a logk+1 n)。
- 如果 f(n) = Ω(n^logb a + ε),其中 ε > 0,且af(n/b) ≤ cf(n),其中 c < 1,那么 T(n) = Θ(f(n))。
对于 T(n) = 9T(n/3) + 5n^2,可以看成a=9,b=3,f(n)=5n^2,因此:
- logb a = log3 9 = 2
- f(n) = O(n^logb a - ε),其中 ε > 0,因为 n^2 = O(n^2+ε),所以 f(n) = O(n^2)
- 因此,T(n) = Θ(n^log3 9) = Θ(n^2)
对于 T(n) = 4T(n/5) + 7n,可以看成a=4,b=5,f(n)=7n,因此:
- logb a = log5 4 < 1
- f(n) = Ω(n^logb a + ε),其中 ε > 0,因为 n^1+ε = Ω(n),所以 f(n) = Ω(n)
- 由于 af(n/b) = 4f(n/5) = 4(7n/5) = 28n/5,而不满足 af(n/b) ≤ cf(n),其中 c < 1,因此无法套用主定理。
- 但是可以使用递归树法来解决,每个节点有4个子节点,每个子节点处理大小为 n/5 的问题,因此每层的贡献为 4*(7n/5),即 28n/5,递归树的高度为 log5 n,因此总复杂度为 Θ(n^log5 4) = Θ(n^0.861),约为O(n)的复杂度。
回答完毕。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)