关于Merge Sort的空间复杂度分析
来源：1-8 归并排序法的复杂度分析
hxcchan
2021-12-30 14:45:21
老师关于归并排序的空间复杂度分析我觉得是O(n)，我是这么分析的：
对于递归树第0层我们假设输入数据的规模是O(n)级别：
第一层的call stack上我们开辟了O(n/2)级别的空间；
第二层开辟了O(n/4)级别的空间，一直到最后一层我们开辟的空间是O(1)；
所以一共加起来是：O(n + n/2 + n/4 + ...+ 1) = O(2n - 1) = O(n)
虽然递归树有两侧，但是执行有面那一侧的时候左面的部分已经执行完毕，call stack全部弹出，所以排序过程中占用的最大内存空间还是O(n)级别。
不知道这样的分析正不正确？谢谢老师！
相关截图：
写回答
1回答
-
赞！完全正确，归并排序的空间复杂度就是 O(n) 的。
在课程后续，我们会看到归并排序的一个优化，我们可以不在 merge 中不断开辟使用的临时空间，而一次性在整个归并排序开始之前，将需要的临时空间全部开出来。而这个空间，我们只需要和原数组大小一样就好。对于这个优化的代码，就可以更清晰地看到，整个归并排序，需要这样的一个 O(n) 的辅助空间：）
继续加油！：）
1
相似问题