空间复杂度混淆

我对分析空间复杂性有点困惑。我不确定“算法占用额外空间”的含义。什么算作1的空间？在这里的例子空间复杂度混淆

int findMin(int[] x) { 
    int k = 0; int n = x.length; 
    for (int i = 1; i < n; i++) { 
     if (x[i] < x[k]) { 
      k = i; 
     } 
    } 
    return k; 
}

的空间复杂度是O（n），并且我猜测这是由于n的阵列大小。

但是对于像heapsort这样的东西，它需要O（1）。不是一个就地heapsort也需要有一个大小为n的数组（n是输入的大小）？或者我们假设输入已经在数组中了？为什么heapsort的空间复杂度为O（1）？

谢谢！

来源

2012-12-27 cinnamon toast

哦，我想我知道了。即使输入不在数组中，我们仍然可以将它作为一个数组存储，它仍然只需要O（1）。 –

如果你解决了你自己的问题，请为你的问题写一个答案，并选择它作为正确的答案。这将有助于其他人在未来找到答案，如果他们有同样的问题。谢谢 – SnareChops

Heapsort只需要恒定的数量辅助存储，因此O(1)。输入使用的空间当然是O(n)。

来源

2012-12-27 06:54:39

实际上，额外的空间对应于算法使用的额外堆栈空间，也就是其他输入，并且通常在递归函数调用中需要堆栈，如果在递归函数中存在递归，肯定会使用堆栈来存储内容，直到它被解决由终止条件。

堆栈的大小为O（递归树的高度）。

希望这是有帮助的！

来源

2013-04-30 03:56:28

空间复杂度混淆

回答

相关问题