1

一般来说，我对分析空间复杂性有点困惑。我不确定“算法占用的额外空间”的含义。什么算作 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。

但是对于像堆排序这样的东西，它需要 O(1)。就地堆排序是否也需要一个大小为 n 的数组（n 是输入的大小）？还是我们假设输入已经在数组中？为什么堆排序的空间复杂度为 O(1)？

谢谢！

4

2 回答 2

1

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

于 2012-12-27T06:54:39.853 回答
0

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

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

希望这有帮助！！

于 2013-04-30T03:56:28.623 回答