让我们以合并排序的实现为例
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 …的n个合并进行记录（或者最好说成1，2，3 … n / 4，n / 2 ，n-它们无法并行化），得出O（n）。它仍然是O（n log n）。在并非如此完美的世界中，您没有无限数量的处理器，上下文切换和同步可以抵消任何潜在的收益。
b）空间复杂度始终为Ω（n），因为您必须将元素存储在某处。在使用数组的实现中，其他的空间复杂度可能是O（n），在链表实现中的可能是O（1）。在实践中，使用列表的实现需要额外的空间用于列表指针，因此，除非您已经在内存中拥有列表，否则就没有关系。
编辑 是否计算堆栈帧，则为O（n）+ O（log n），如果是数组，则仍为O（n）。对于列表，它是O（log n）附加内存。
c）列表只需要在合并过程中更改一些指针。这需要不断增加的内存。
d）这就是为什么在合并排序复杂性分析中人们提到“附加空间需求”或类似的东西的原因。显然，您必须将元素存储在某个位置，但是始终最好提一下“其他内存”以阻止纯粹主义者。
