algorithm - 合并排序如何在最坏情况下具有 O(n) 的空间复杂度？

Question

O(n) 复杂度意味着合并排序在最坏的情况下占用的内存空间等于初始数组中存在的元素数。但是它在进行递归调用时不是创建了新数组吗？那个空间怎么不算？

Answer 1

如果在递归调用自身之前在 mergesort() 中分配数组的两半，自顶向下合并排序的最坏情况可能比原始数组占用更多空间。

更有效的自上而下合并排序使用一个入口函数，该函数一次性分配临时缓冲区，将临时缓冲区的地址作为参数传递给一对相互递归函数中的一个，该函数生成索引并在两个数组。

在自下而上合并排序的情况下，可以使用原始数组大小的 1/2 的临时数组，合并数组的两半，以临时数组中的前半部分数据结束，并且原始数组中的后半部分，然后最终合并回原始数组。

然而，在任何一种情况下，空间复杂度都是 O(n)，因为像 2 或 1/2 这样的常量对于大 O 会被忽略。