为什么递归合并排序优先于迭代合并排序，即使后者具有辅助空间复杂性？
在研究合并排序算法时，我很想知道这个排序算法是否可以进一步优化。发现合并排序算法存在迭代版本，具有相同的时间复杂度，但O(1)空间复杂度更好。从性能上看，迭代方法总是比递归方法更好。那么，为什么它不那么常见，而且很少在任何常规算法课程中讨论？下面是迭代合并排序算法的链接
回答 3
Stack Overflow用户
发布于 2021-03-18 17:22:06
如果您认为它具有O(1)空间复杂性，请再看一遍。它们具有大小为A的原始数组n，以及大小为n的辅助temp。(它实际上只需要是n/2，但他们保持了它的简单。)
他们需要第二个数组的原因是，当您合并时，您将底部区域复制到temp中，然后从原来的位置开始合并。
所以权衡就是这样。递归解决方案涉及的细节要少得多，概念更加清晰，但在两个解决方案共享的O(n)内存开销之上增加了一个O(n)内存开销。当你试图传达概念时，这是一次直接的胜利。
此外，在实践中，我认为递归也是一场胜利。
在迭代方法中，您一直对整个数组进行完整的遍历。在大型数组的情况下，这意味着数据进入缓存进行传递，然后被操作，然后在加载数组的其余部分时脱落。只需要在下一次传递时再次加载。
相反，在递归方法中，对于相当于前几次传递的操作，您将它们加载到缓存中，对它们进行完全排序，然后继续。(获得这次胜利的次数在很大程度上取决于数据类型、内存布局和CPU缓存的大小。)您只是在合并太多数据时才从缓存加载/卸载数据，而不适合缓存。算法课程通常忽略了这些低层次的细节，但它们对现实世界的性能影响很大。
Stack Overflow用户
发布于 2021-03-18 17:18:53
发现合并排序算法具有相同时间复杂度的迭代版本，但O(1)空间复杂度更好。
您链接到的合并排序的迭代、自下而上的实现没有O(1)空间复杂性。它维护数组的副本，因此表示O(n)空间的复杂性。因此，额外的O(logn)堆栈空间(用于递归实现)与总体空间复杂度无关。
在你问题的标题和一些评论中，你使用了“辅助空间复杂性”这个词。这就是我们通常所说的空间复杂性，但你似乎认为这个术语意味着恒定的空间复杂性。这不是真的。“辅助”是指输入所使用的空间以外的空间。这个术语并没有告诉我们实际的复杂性。
Stack Overflow用户
发布于 2021-03-18 17:58:33
递归自上而下的合并排序主要是教育性质的。大多数实际库使用混合插入排序和自下而上合并排序的一些变化，使用插入排序创建将在偶数次合并传递中合并的小排序运行，从而使原始数组和临时数组之间的合并以原始数组中的排序数据结束(除了在数组末尾运行单一实例之外，没有复制操作，可以通过为插入排序选择适当的初始运行大小来避免复制操作(注意--在我的示例代码中没有这样做，我只使用run size 32或64，而更高级的方法，比如Tim排序确实选择了适当的运行大小)。
自下而上的速度略快一些，因为数组指针和索引将保存在寄存器中(假设是优化的编译器)，而自顶向下则是将数组指针和索引从堆栈中弹出。
虽然我不确定OP实际上意味着合并排序的O(1)空间复杂度，但这是可能的，但它比传统的合并排序( O(n)辅助空间)慢50%左右。现在这主要是一项研究(教育)工作。代码相当复杂。链接到示例代码。其中一个选项根本不是额外的缓冲区。基准表用于相对较少的键数(最大为32767键)。对于大量的键，这个示例的速度比优化的插入+自下而上的合并排序慢了大约50% (std::stable_sort是广义的，例如对每个比较使用指针函数，因此没有完全优化)。
https://github.com/Mrrl/GrailSort
示例混合插入+自下而上的合并排序C++代码(省略了原型)：
void MergeSort(int a[], size_t n) // entry function
{
if(n < 2) // if size < 2 return
return;
int *b = new int[n];
MergeSort(a, b, n);
delete[] b;
}
void MergeSort(int a[], int b[], size_t n)
{
size_t s; // run size
s = ((GetPassCount(n) & 1) != 0) ? 32 : 64;
{ // insertion sort
size_t l, r;
size_t i, j;
int t;
for (l = 0; l < n; l = r) {
r = l + s;
if (r > n)r = n;
l--;
for (j = l + 2; j < r; j++) {
t = a[j];
i = j-1;
while(i != l && a[i] > t){
a[i+1] = a[i];
i--;
}
a[i+1] = t;
}
}
}
while(s < n){ // while not done
size_t ee = 0; // reset end index
size_t ll;
size_t rr;
while(ee < n){ // merge pairs of runs
ll = ee; // ll = start of left run
rr = ll+s; // rr = start of right run
if(rr >= n){ // if only left run
rr = n; // copy left run
while(ll < rr){
b[ll] = a[ll];
ll++;
}
break; // end of pass
}
ee = rr+s; // ee = end of right run
if(ee > n)
ee = n;
Merge(a, b, ll, rr, ee);
}
std::swap(a, b); // swap a and b
s <<= 1; // double the run size
}
}
void Merge(int a[], int b[], size_t ll, size_t rr, size_t ee)
{
size_t o = ll; // b[] index
size_t l = ll; // a[] left index
size_t r = rr; // a[] right index
while(1){ // merge data
if(a[l] <= a[r]){ // if a[l] <= a[r]
b[o++] = a[l++]; // copy a[l]
if(l < rr) // if not end of left run
continue; // continue (back to while)
while(r < ee) // else copy rest of right run
b[o++] = a[r++];
break; // and return
} else { // else a[l] > a[r]
b[o++] = a[r++]; // copy a[r]
if(r < ee) // if not end of right run
continue; // continue (back to while)
while(l < rr) // else copy rest of left run
b[o++] = a[l++];
break; // and return
}
}
}
size_t GetPassCount(size_t n) // return # passes
{
size_t i = 0;
for(size_t s = 1; s < n; s <<= 1)
i += 1;
return(i);
}https://stackoverflow.com/questions/66695718
复制相似问题
腾讯云开发者
