下面这段代码的空间复杂度？

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^2)

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

可能的解释是什么？

Answer 1

解释你的解释是正确的。空间复杂度是线性的。但是，您的结论（以及本书作者的结论）是错误的。正确答案是两个答案都正确。也就是说，空间复杂度是：O(n)和O(n^2)Big-O 给出了一个上限，而不是确切的界限。想想它<=而不是 just&nbsp;=。因此，如果a in O(n)它也是真的a in O(n^2)（从数学上讲，Big-O 给出了一组函数）。精确界限由Theta&nbsp;(&nbsp;=) 给出，下界由Omega&nbsp;(&nbsp;>=) 给出，严格下界由small-omega&nbsp;(&nbsp;>) 给出，严格上限由small-o&nbsp;(&nbsp;<) 给出。所以空间复杂度在Theta(n).有关详细信息和实际数学定义，请参阅维基百科。笔记如果我们假设 Java 的垃圾收集器处于活动状态，则空间复杂度仅为线性。可以禁用它或用实际上不释放内存的模拟实现替换它（请参阅Epsilon-GC）。在那种情况下，空间复杂度确实是二次的。算法本身需要分配二次方的内存。但是，它只会同时持有线性数量的内存。空间复杂度分析通常是根据必须同时保留多少内存来完成的。但也许作者想分析算法总共需要分配多少，这也可以解释他的选择。

Answer 2

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