不对,答案是0( NlogN)
时间: 2024-03-30 18:38:13 浏览: 18
非常抱歉,我的回答有误。正确答案应该是 O(NlogN)。
根据递归式,可以得到:
T(N) = 2T(N/2) + N/2
对其进行递归展开,可以得到:
T(N) = 2(2T(N/4) + N/4) + N/2
= 2^2T(N/2^2) + 2N/4 + N/2
= 2^2T(N/2^2) + 3N/4
继续展开,可以得到:
T(N) = 2^kT(N/2^k) + kN/2^k
当 N/2^k = 1 时,即 k = log2(N),此时递归结束。将 k = log2(N) 代入上式,可以得到:
T(N) = 2^log2(N)T(1) + Nlog2(N)/N
= N + Nlog2(N)
= O(NlogN)
因此,用0表示的时间复杂度为 O(NlogN)。非常感谢您指出我的错误。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![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)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![whl](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)