请用分治策略设计递归的归并排序算法,并分析其时间复杂性(要求:分别给出divide、conquer、combine这三个阶段所花的时间,并在此基础上列出递归方程,最后用套用公式法求出其解的渐进阶)。
正确答案:
![](https://img.274949.com/Images/2020-04/06/iewtw90q.jpg)
Divide阶段的时间复杂性:O(1)
Conquer阶段的时间复杂性:2T(n)
Combine阶段的时间复杂性:Θ(n)
![](https://img.274949.com/Images/2020-04/06/9f11x0xi.jpg)
用套用公式法:a=2,b=2,nlogba=n,f(n)=n,因为f(n)与nlogba同阶
∴T(n)=Θ(nlogn)
![](https://img.274949.com/Images/2020-04/06/iewtw90q.jpg)
Divide阶段的时间复杂性:O(1)
Conquer阶段的时间复杂性:2T(n)
Combine阶段的时间复杂性:Θ(n)
![](https://img.274949.com/Images/2020-04/06/9f11x0xi.jpg)
用套用公式法:a=2,b=2,nlogba=n,f(n)=n,因为f(n)与nlogba同阶
∴T(n)=Θ(nlogn)
答案解析:有
![](/editor/images/201705/qrcode_for_gh_573e2a458573_258.jpg)
微信扫一扫手机做题