合并排序时间和空间的复杂性
让我们以这个Merge Sort的实现为例
void mergesort(Item a[], int l, int r) {
if (r <= l) return;
int m = (r+l)/2;
mergesort(a, l, m); ------------ (1)
mergesort(a, m+1, r); ------------(2)
merge(a, l, m, r);
a）此合并排序的时间复杂度为O（nlg（n））。 并行化（1）和（2）会带来什么实际收益？ 从理论上看，在将它们并行化之后，你最终会以O（nlg（n））结束，但实际上我们能得到什么收益？
b）此合并排序的空间复杂度为O（n）。 但是，如果我选择使用链接列表执行就地合并排序（不确定是否可以合理地使用数组完成），则空间复杂度将变为O（lg（n）），因为您必须考虑递归堆栈帧大小？ 我们可以把O（lg（n））视为常数，因为它不能超过64？ 我可能在几个地方误解了这一点。 64的意义究竟是什么？
c）http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html说合并排序需要使用链接列表的恒定空间。 怎么样 ？ 他们是否把O（lg（n）不变？
d）[为了获得更多清晰度而添加]为了空间复杂度计算，假定输入数组或列表已经在内存中是公平的吗？ 当我做复杂性计算时，除了输入已经占用的空间之外，我总是会计算我将需要的“额外”空间。 否则，空间复杂度将始终为O（n）或更差。
a）是的 - 在一个完美的世界中，你必须记录n，n / 2，n / 4 ...的合并（或者更好地说1,2,3 ... n / 4，n / 2 ，n - 它们不能并行化），这就给出了O（n）。 它仍然是O（n log n）。 在不太完美的世界中，您没有无限数量的处理器和上下文切换和同步偏移量来获得任何潜在收益。
b）空间复杂度总是Ω（n），因为你必须将元素存储在某处。 在使用数组的实现中以及在链表实现中使用O（1）时，额外的空间复杂度可以是O（n）。 在实践中，使用列表的实现需要列表指针的额外空间，所以除非你已经在内存中拥有这个列表，否则它应该不重要。
编辑如果你计数堆栈帧，那么它是O（n）+ O（log n），所以在数组的情况下仍然是O（n）。 在列表的情况下，它是O（log n）额外的内存。
c）列表只需要在合并过程中更改一些指针。 这需要不断增加的内存。
d）这就是为什么在合并分类复杂度分析中，人们提到'额外的空间需求'或类似的东西。 很显然，你必须在某个地方储存这些元素，但最好提及“额外记忆”以保持纯粹主义者的地位。
MergeSort时间复杂性是O（nlgn），这是一个基础知识。 合并排序空间复杂度将始终为O（n），包括数组。 如果你画空间树，看起来好像空间复杂度是O（nlgn）。 但是，由于代码是深度优先代码，因此总是只沿树的一个分支进行扩展，因此，所需的总空间使用总是以O（3n）= O（n）为界。
例如，如果你画空间树，看起来好像是O（nlgn）
16 | 16
/
/
/
/
8 8 | 16
/ /
/ /
4 4 4 4 | 16
/ / / /
2 2 2 2..................... | 16
/ / ........................
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 | 16
树的高度为O（logn）=>空间复杂度为O（nlogn + n）= O（nlogn）。 但是，实际代码并非如此，因为它并不是并行执行的。 例如，在N = 16的情况下，这是mergesort的代码执行的方式。 N = 16。
16
/
8
/
4
/
2
/
1 1
注意如何使用空间的数量是32 = 2n = 2 * 16 <3n
然后它向上合并
16
/
8
/
4
/
2 2
/
1 1
这是34 <3n。 然后它向上合并
16
/
8
/
4 4
/
2
/
1 1
36 <16 * 3 = 48
然后它向上合并
16
/
8 8
/
4 4
/
2 2
/
1 1
16 + 16 + 14 = 46 <3 * n = 48
在更大的情况下，n = 64
64
/
32 32
/
16 16
/
8 8
/
4 4
/
2 2
/
1 1
这是64 * 3 <= 3 * n = 3 * 64
你可以通过一般情况下的归纳来证明这一点。
因此，即使用数组实现，只要在合并后清理已用空间，而不是并行但顺序执行代码，空间复杂度总是以O（3n）= O（n）为界。
我的实施例如下：
templace<class X>
void mergesort(X a[], int n) // X is a type using templates
{
if (n==1)
{
return;
}
int q, p;
q = n/2;
p = n/2;
//if(n % 2 == 1) p++; // increment by 1
if(n & 0x1) p++; // increment by 1
// note: doing and operator is much faster in hardware than calculating the mod (%)
X b[q];
int i = 0;
for (i = 0; i < q; i++)
{
b[i] = a[i];
}
mergesort(b, i);
// do mergesort here to save space
// http://stackoverflow.com/questions/10342890/merge-sort-time-and-space-complexity/28641693#28641693
// After returning from previous mergesort only do you create the next array.
X c[p];
int k = 0;
for (int j = q; j < n; j++)
{
c[k] = a[j];
k++;
}
mergesort(c, k);
int r, s, t;
t = 0; r = 0; s = 0;
while( (r!= q) && (s != p))
{
if (b[r] <= c[s])
{
a[t] = b[r];
r++;
}
else
{
a[t] = c[s];
s++;
}
t++;
}
if (r==q)
{
while(s!=p)
{
a[t] = c[s];
s++;
t++;
}
}
else
{
while(r != q)
{
a[t] = b[r];
r++;
t++;
}
}
return;
}
希望这有助于！=）
不久Chee Loong，
多伦多大学
a）是的，当然，并行合并排序可能会非常有益。 它仍然是nlogn，但你的常数应该大大降低。
b）具有链表的空间复杂度应该是O（n），或者更具体地说是O（n）+ O（logn）。 请注意，这是一个+，而不是*。 进行渐近分析时不要过多关注常数。
c）在渐近分析中，只有方程中的主导项很重要，所以我们有+而不是*的事实使它成为O（n）。 如果我们重复遍历子列表，我相信这将是O（nlogn）空间 - 但是一个智能的基于链表的合并排序可以共享列表的区域。
链接地址: http://www.djcxy.com/p/39689.html