合并排序时间和空间复杂性

  • Z时代
  • 2024-01-10
  • 分类：问答

让我们以合并排序的实现为例

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）这就是为什么在合并排序复杂性分析中人们提到“附加空间需求”或类似的东西的原因。显然，您必须将元素存储在某个位置，但是始终最好提一下“其他内存”以阻止纯粹主义者。

以上是 合并排序时间和空间复杂性 的全部内容， 来源链接： utcz.com/qa/412119.html

回到顶部