二、请证明当 T(n) = 2T(n/2)+n, T(1) = 0 时, T(n) = nlog2(n), 假设 n 是 2 的指数倍
时间: 2023-12-26 09:04:22 浏览: 42
证明:
当 n=1 时,T(1) = 0,结论成立。
假设 n=k 时结论成立,即 T(k)=klog2(k)。
当 n=2k 时,有:
T(2k) = 2T(k) + 2k
= 2klog2(k) + 2k
= 2k(log2(k)+1)
= 2klog2(2k)
因此,当 n=2的指数倍时,有 T(n) = nlog2(n)。
综上所述,当 T(n) = 2T(n/2)+n, T(1) = 0 时,对于 n 是 2 的指数倍,有 T(n) = nlog2(n)。
相关问题
请编写程序证明当 T(n) = 2T(n/2)+n, T(1) = 0 时, T(n) = nlog2(n), 假设 n 是 2 的指数倍
我们可以使用数学归纳法来证明这个递归式的解为 T(n) = nlog2(n)。
首先,当 n=1 时,T(1) = 0,成立。
然后,假设当 n=k 时,T(k) = klog2(k) 成立,即:
T(k) = 2T(k/2) + k = 2(k/2log2(k/2)) + k = klog2(k) - k + k = klog2(k)
现在我们来考虑 n=2k 时的情况,即 T(2k) = 2T(k) + 2k。
根据假设,T(k) = klog2(k),所以 T(2k) = 2klog2(k) + 2k = 2k(log2(k) + 1) = 2klog2(2k)。
因此,由数学归纳法可知,对于所有 n=2的指数倍,T(n) = nlog2(n) 成立。
T(n) = 2T(n/2) + nlogn的asymptotically tight bound
我们可用主定理(Master Theorem)来证明T(n) = 2T(n/2) 的时间复杂度为nlogn的asymptotically tight bound。
根据主定理,对于递归式T(n) = aT(n/b) + f(n)(其中a和b为常数,且f(n)为渐进正的函数):
如果f(n) = O(n^log[b]a-ε) 对某个常数ε > 0,则T(n) = Θ(n^log[b]a)。
如果f(n) = Θ(n^log[b]a * logk n),则T(n) = Θ(n^log[b]a * logk+1 n) 。
如果f(n) = Ω(n^log[b]a+ε) 对某个常数ε > 0,并且如果对某个常数c < 1和足够大的n,有af(n/b) ≤ cf(n),则T(n) = Θ(f(n)) 。
在这里,a = 2,b = 2,f(n) = 0,因此f(n) = Θ(n^0),即 f(n) = Θ(1)。
因为 f(n) = Θ(1) = Θ(n^0),所以我们可以应用主定理的第一种情况来计算时间复杂度,即:
T(n) = Θ(n^log[b]a) = Θ(n^log[2]2) = Θ(nlogn)
证毕。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)
![](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)