algorithm - 不可变数组中归并排序的空间复杂度

Question

归并排序的空间复杂度为 O(n)，方法如下void sort(int[] arr)。

如果我创建一个方法int[] sort(int[] arr)，它不修改输入数组，而是返回一个新的排序数组，那么这个方法/算法的空间复杂度是多少？

标签： algorithmspace-complexity

Answer 1

取决于合并排序的实现。

递归的

由于您无法在每个递归调用中更改输入数组，因此算法的空间复杂度为S(n) = 2S(n/2) + n. 因此，S(n) = Theta(n log n)。

迭代的

如果合并排序的实现不是递归的（迭代合并排序），您可以将输入数组复制到一个可变数组中，并就地对该数组进行排序。因此，这种合并排序实现的空间复杂度为Theta(n)。