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

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 =。因此，如果a in O(n)它也是真的a in O(n^2)（从数学上讲，Big-O 给出了一组函数）。

精确界限由Theta ( =) 给出，下界由Omega ( >=) 给出，严格下界由small-omega ( >) 给出，严格上限由small-o ( <) 给出。所以空间复杂度在Theta(n).

有关详细信息和实际数学定义，请参阅维基百科。

---

笔记

如果我们假设 Java 的垃圾收集器处于活动状态，则空间复杂度仅为线性。可以禁用它或用实际上不释放内存的模拟实现替换它（请参阅Epsilon-GC）。

在那种情况下，空间复杂度确实是二次的。

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

Answer 2

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