java - 空间复杂度示例

Question

所以我想知道当对象(或基元)在 for 循环内创建时，这对空间复杂度有何贡献？

例如，这是一个代码示例:

public boolean checkUnique(String p){
    int term = -1;
    int len = p.length();
    for (int i =0; i<len; i++) {
        char c = p.charAt(i);
        StringBuilder sb = new StringBuilder(p.substring(0, i));
        sb.append(p.substring(i+1, len));
        String str = sb.toString();
        if (str.indexOf(c) != term) {
            return false; 
        }
    }
    return true;
}

所以我试图分析这个算法的空间复杂度。看起来是O(n)。这是我的推理:迭代次数等于输入大小，并且在每次迭代中我们都创建一个 StringBuilder 对象，因此我们创建与输入大小成比例的 StringBuilder 对象。同样的推理也适用于我们在每次迭代中创建 String 对象和 char 的事实。这个推理正确吗？

我问的原因是因为我遇到了一种算法，其中每次迭代后都会进行以下分配:

int val = str.charAt(i);

然而该算法的空间复杂度为 O(1)。那么我的理解一定是错误的？在这种情况下，checkUnique 算法的空间复杂度也为 O(1)。

Answer 1

为了进行复杂性分析，您必须非常清楚您的机器是如何工作的。机器将如何运行您的代码？该机器的功能是什么？

运行该代码的机器至少有两种非常相似的工作方式，每种方式都会对您的问题产生不同的答案。

假设每个新的变量声明都会导致分配一个唯一的内存位，并且一旦分配，该内存就无法重复使用。这可能就像磁带存储器，或者就像您用墨水在纸上写下步骤。如果您这样做，空间复​​杂度确实与循环迭代次数成正比，因为您在循环体中分配内存。

相反，假设新变量声明使用分配的第一个可用内存位，并且一旦变量超出范围，该内存就会被释放并可以自由地重新分配。在这种情况下，到函数结束时，除了恒定数量的变量之外的所有变量都已超出范围，因此空间复杂度是恒定的。

Java 具有自动垃圾收集功能，因此我们可以合理地说我们处于第二种情况，甚至是 w.r.t。堆分配的内存(堆栈分配的内存，就像基元一样，肯定以第二种方式工作)。实际上，垃圾收集可能不会在所有情况下立即发生，因此我们可能会介于两种情况之间。但在令人满意的情况下，我们可以有把握地说，在 Java 中，这是 O(1)。

在 C++ 中，情况会有所不同。在那里，我们需要new和delete(或等效的)我们的堆分配内存才能处于第二种情况；否则，我们就会是第一!

正如您所看到的，很大程度上取决于代码的真正含义，这只能根据其执行的系统来完全理解。