老师帮忙分析一下归并排序的空间复杂度？

Question

讨论1.6 算法3的空间复杂度是多少？老师参与

具体来说，这个问题分两部分：

由于递归而产生的空间复杂度是多少？

算法的整体空间复杂度一共是多少？

不要只写结论，要写清楚推导过程哦~~

算法三就是求最大项数和的优化算法，和归并排序一样的。虽然说推导过程不需要过分追究，但是就有老师出变态题，如上题。递归产生的空间复杂度列出了公式S(N)=S(N/2)+S(N/4)+S(N/8).......+O(1)，接下来就不知道怎么弄了。根据网上资料总体为O(n)，递归所产生的为O(logn)。

Answer 1

liuyubobobo 2018-03-09 17:00:26

归并排序整体只需要设立一个长度为n的辅助空间，就可以完成所有的在递归调用中的merge过程。具体实现可以参考我的代码：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/Optional-01-MergeSort-Create-aux-Array-Out-of-Merge/MergeSort2.h

其中的aux即为这个辅助空间。他的大小为O(n)的。

递归过程，系统会开辟递归栈空间，这个空间的大小和递归深度成正比。归并排序过程从n个元素，向下递归，每次递归调用，数据量减半，所以整个递归深度为logn。这就是递归产生的空间为O(logn)的来源。

整体，归并排序的空间复杂度为O(n+logn)。不过对于大O符号，低阶项可以省略，整体，归并排序的空间复杂度为O(n)。

最后，我详细回答这个问题，是因为这个问题和课程相关。和课程内容无关的作业题，即使是算法领域，我也不帮助进行答疑哦。谢谢谅解：）