Space 下面这段代码的复杂度？

Question

我在做面试准备时遇到了这个问题。

public class Main {
    public static void main(String[] args) {
        // n is some user input value
        int i = 0;
        while (i < n) {
            int[] a = new int[n];
            for (int j = 0; j < n; j++){
                a[j] = i * j;
            }
            i++;
        }
    }
}

给出的选择是：

O(n)
O(n^2)

根据我的理解，答案应该是 O(n)，因为在每次迭代中都会创建数组的新实例，并且会丢失先前的引用。然而，书中提到的答案是 O(n^2)。

可能的解释是什么？

Answer 1

这本书似乎完全错了。执行所需的 space 是 O(n)。至于可能的解释：作者考虑到了运行时的复杂性。嵌套循环给出了 O(n^2) 运行时复杂度。如果这本书比较新且流行，它可能有一个勘误网页，这可能会阐明它。

Answer 2

说明

你的解释是正确的。 space 复杂度为线性。

但是，您的结论（以及本书作者的结论）是错误的。正确答案是两个答案都是正确的。也就是说，space 的复杂性在于：

O(n) 和
O(n^2)

Big-O 给出了 upper-bound，而不是确切的界限。将其视为 <= 而不是 =。因此，如果 a in O(n) a in O(n^2) 也是正确的（从数学上讲，Big-O 给出了一组函数）。

确切界限由 Theta (=) 和下限 Omega (>=), 严格的下限由 small-omega (>) 和严格的上限由 small-o（<）。所以 space 复杂度在 Theta(n).

有关详细信息和实际数学定义，请参阅 Wikipedia。

备注

如果我们假设 Java 的垃圾收集器是 活动的 ，那么 space 的复杂度仅为线性。可以禁用它或用实际上不释放内存的模拟实现替换它（参见 Epsilon-GC）。

在那种情况下，space 复杂度确实是 二次方。

算法本身需要分配二次方的内存量。但是，它只会同时容纳 linear 的内存量。 Space 复杂性分析通常是根据必须同时保留多少内存来完成的。但也许作者想分析一下总共需要分配多少的算法，这也可以解释他的选择。

Space 下面这段代码的复杂度？

Space complexity of the piece of code below?

java

space-complexity

说明

备注