Fra*_* Q. 24 algorithm time-complexity space-complexity
我们以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)或更差.
Che*_*oon 58
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,
多伦多大学
sou*_*eck 18
a)是的 - 在一个完美的世界中,你必须进行大小为n,n/2,n/4的log n合并...(或更好地表示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)这就是为什么在合并 - 排序复杂性分析中人们提到"额外的空间需求"或类似的东西.很明显,你必须将元素存储在某个地方,但最好提一下"额外的记忆"来保持纯粹主义者的存在.