空间复杂性示例

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有自动垃圾收集,所以我们可以合理地说我们在第二种情况下甚至是堆分配的内存(堆栈分配的内存,就像基元一样,肯定是以第二种方式工作).实际上,垃圾收集可能不会在所有情况下立即发生,因此我们可能介于两种情况之间.但在幸福的情况下,我们可以安全地说,在Java中,这是O(1).

在C++中,故事会有所不同.在那里,我们需要new和delete(或等效)我们的堆分配内存在第二个场景中; 否则,我们会在第一个!

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