请用分治策略设计递归的归并排序算法，并分析其时间复杂性（要求：分_睦霖题库

简答题请用分治策略设计递归的归并排序算法，并分析其时间复杂性（要求：分别给出divide、conquer、combine这三个阶段所花的时间，并在此基础上列出递归方程，最后用套用公式法求出其解的渐进阶）。

正确答案：
Divide阶段的时间复杂性：O（1）
Conquer阶段的时间复杂性：2T（n）
Combine阶段的时间复杂性：Θ（n）

用套用公式法：a=2，b=2，n^logb^a=n，f（n）=n，因为f（n）与n^logb^a同阶
∴T（n）=Θ（nlogn）
答案解析：
关注下方微信公众号，在线模考后查看

热门试题