我在网上看到很多mergesort的实现，比如https://www.geeksforgeeks.org/merge-sort/传入参数 l、m 和 r 以了解子数组的开始和结束位置。我想知道如果我们复制子数组并将其传入，运行时和空间复杂度是否会保持不变。示例建议代码如下:
class Solution {
//mergeSort implementation
public int[] sortArray(int[] nums) {
if (nums.length == 1) {
return nums;
}
int arrayLength = nums.length;
// make copies instead of passing indices
int[] left = Arrays.copyOfRange(nums, 0, arrayLength/2);
int[] right = Arrays.copyOfRange(nums, arrayLength/2, arrayLength);
left = sortArray(left);
right = sortArray(right);
return merge(left, right);
}
public int[] merge(int[] left,int[] right) {
int[] merged = new int[left.length + right.length];
int mergedCounter = 0;
int i = 0; //leftCounter
int j = 0; //rightCounter
while (mergedCounter != left.length + right.length) {
if (i == left.length) {
merged[mergedCounter] = right[j];
mergedCounter++;
j++;
} else if (j == right.length) {
merged[mergedCounter] = left[i];
mergedCounter++;
i++;
} else {
if (left[i] <= right[j]) {
merged[mergedCounter] = left[i];
mergedCounter++;
i++;
} else {
merged[mergedCounter] = right[j];
mergedCounter++;
j++;
}
}
}
return merged;
}
}
我相信运行的复杂性并没有增加，因为制作一个副本所花费的运行时间与通过 new int[n] 初始化一个 n 长度的新数组所花费的运行时间相同。这部分问题还包括一个 O(n) 合并子函数，所以没关系。
我也相信空间复杂度保持不变。当我们在递归调用中创建两个临时子数组时，将在合并步骤中创建与使用指向 l、m 和 r 的指针的在线解决方案中指定的相同数量的空间。
我的思维过程是否有效，还是我遗漏了什么？
最佳答案
任何额外的复制操作都会增加运行时间。制作子数组的副本将增加一个常数的空间需求，但由于“复杂性”忽略常数和/或低阶项，空间“复杂性”将保持不变。
大多数库使用自下而上合并排序的一些变体，其中索引(或指针)动态更新，而不是通过递归传递，并且通常根据编译器优化保存在寄存器中。自上而下的合并排序主要用作学习练习。
对于自下而上的归并排序，可以通过改 rebase 于归并传递的归并方向，或者对于自上而下的归并排序，基于递归级别来改变归并方向，从而最大限度地减少复制操作。
对于 C/C++，传递数组和索引的替代方法是传递指针或迭代器，将每次调用所需的参数数量减少 1 个参数。
关于algorithm - 进行合并排序时是否有必要将索引作为参数传递？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56928411/