我们以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)或更差.