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

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++;
        }
    }
}

给出的选择是：

1. 在）
2. O(n^2)

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

什么是可能的解释？

Answer 1

解释

你的解释是正确的。空间复杂度是线性的。

然而，你的结论（以及书籍作者的结论）是错误的。正确答案是两个答案都是正确的。也就是说，空间复杂度同时存在于：

• O(n)和
• O(n^2)

Big-O 给出了上限，而不是精确的界限。考虑一下它而<=不是仅仅=。因此，如果a in O(n)这也成立a in O(n^2)（在数学上，Big-O 给出了一组函数）。

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

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

笔记

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

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

该算法本身需要分配二次量的内存。然而，它只能同时保存线性数量的内存。空间复杂度分析通常是针对必须同时保存多少内存来进行的。但也许作者想分析算法总共需要分配多少，这也可以解释他的选择。