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

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. O(n)
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) .

参见 Wikipedia了解更多信息和实际的数学定义。

---

注意事项

如果我们假设 Java 的垃圾收集器是 Activity 的，则空间复杂度只是线性。可以禁用它或用实际上不释放内存的模拟实现替换它(参见 Epsilon-GC )。

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

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