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

Question

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

5

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

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)。

可能的解释是什么？

- amitection

1

算法不一定能够在常量内存下成功完成，因为用户可能会在这种情况下输入任意大的 n 值。（不考虑 int 的最大值等）当分析复杂度时，通常只考虑算法本身，而不考虑 JVM 特定的实现细节，如垃圾收集算法。该算法分配了大小为 n 的数组，共 n 次。因此，空间复杂度为 O(n)。 - aioobe

在这种特定情况下，我甚至会认为JIT会意识到a是一个循环局部变量，而且n在循环中不会改变，因此可能每次迭代都重用相同的数组。 - aioobe

1

@aioobe：“通常不考虑JVM特定的实现细节，比如垃圾回收算法” - 这难道不意味着我们必须假设数组永远不会被释放，因此我们需要O(n^2)的内存吗？还是你只是指特定的算法？ - Thomas

如果您想得到一个明确的答案，OP，您需要提供更多的上下文。书中关于O(n^2)的具体内容是什么？如果没有这个，你只会得到一些猜测。 - aioobe

1

是的，我认为这种推理是有缺陷的。你应该让他/她知道，可以被垃圾回收器收集的内存从实质上来说可以被视为自由的。如果他想要考虑到GC的细节，那么他将会进入痛苦的世界，因为有许多不同的GC算法和许多不同的GC选项需要考虑。或者更好的方法是，给他/她传递这个问题的链接:-)也许他/她能为我们所有人提供一个答案。 - aioobe

显示剩余4条评论

2个回答

1

这本书似乎是错误的。执行所需的空间是O(n)，而不是书中所说的O(1)。关于可能的解释：作者考虑的是运行时间复杂度。嵌套循环导致了O(n^2)的运行时间复杂度。如果这本书比较新且受欢迎，可能会有勘误网页，可以帮助解决问题。

- Slawomir Chodnicki

我认为这并没有被定义，因为内存分配过程的行为是未知或未定义的。每次解引用和后续数组分配都可能分配新的内存或重复使用旧的内存，这取决于优化、内存管理器的工作方式、正在使用的垃圾收集器以及垃圾收集参数。 - rghome

1

@rghome，在讨论Java问题时唯一权威的参考资料是Java语言规范。根据该规范，对于垃圾回收而言，可被回收的内存实际上被视为自由空间。 - aioobe

这对我来说不是一个诡计问题。应该允许合理的假设。 - Slawomir Chodnicki

从技术上讲，一个在 O(n) 中的东西也在 O(n^2) 中。这是一个正确的说法。精确的界限由 Theta 给出，而不是由大 O 给出。 - Zabuzard

@aioobe 我们都知道，“free”内存仍然占用空间，并且需要物理内存，直到它被重新使用或压缩。Java认为它是自由的这一事实只是一个角度。 - rghome

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Zabuzard · Accepted Answer

解释

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

然而，您的结论（以及书的作者的结论）是错误的。正确的答案是两个答案都正确。也就是说，空间复杂度既是：

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）。

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

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