Divide阶段的时间复杂性：O（1）
Conquer阶段的时间复杂性：2T（n）
Combine阶段的时间复杂性：Θ（n）
用套用公式法：a=2，b=2，nlogba=n，f（n）=n，因为f（n）与nlogba同阶
∴T（n）=Θ（nlogn）
（简答题）
请用分治策略设计递归的归并排序算法，并分析其时间复杂性（要求：分别给出divide、conquer、combine这三个阶段所花的时间，并在此基础上列出递归方程，最后用套用公式法求出其解的渐进阶）。
正确答案
Divide阶段的时间复杂性：O（1）
Conquer阶段的时间复杂性：2T（n）
Combine阶段的时间复杂性：Θ（n）
用套用公式法：a=2，b=2，nlogba=n，f（n）=n，因为f（n）与nlogba同阶
∴T（n）=Θ（nlogn）
答案解析
略
相似试题
（简答题）
简述归并排序算法和快速排序算法的分治方法。
（简答题）
算法设计中的分治策略、贪心策略、动态规划策略、回溯策略以及分支定界策略的基本思想是什么？
（判断题）
分治法的解决问题的思想和用递归来描述算法有着某种内在的联系。
（填空题）
已知一个分治算法耗费的计算时间T（n），T（n）满足如下递归方程： 解得此递归方可得T（n）=O（）。
（简答题）
请用伪代码给出求解斐波那契数的递归算法。
（简答题）
请用递归算法，求1+2+3+...n，n由键盘输入。
（简答题）
写出快速排序的非递归调用算法。
（简答题）
如果修改归并排序算法，将数组分成1/3和2/3大小不等的两部分，分别排序后再归并，算法的最坏时间复杂度有什么变化？
（填空题）
序列4 ，2 ，5 ，3 ，8 ，6 ，7，9，采用归并排序算法（升序），经一趟归并后，序列的结果（）。
