嵌套循环的空间复杂度

Question

当谈到算法的空间复杂度时，我感到很困惑。理论上，它对应于算法使用的额外堆栈空间，即输入以外的空间。然而，我很难指出这到底是什么意思。

例如，如果我有一个以下的强力算法来检查数组中是否没有重复项，这是否意味着它使用 O(1) 额外的存储空间，因为它使用 int j 和 int k？

 public static void distinctBruteForce(int[] myArray) {
    for (int j = 0; j < myArray.length; j++) {
        for (int k = j + 1; k < myArray.length; k++) {
            if (k != j && myArray[k] == myArray[j]) {
                return;
            }
        }
    }
}

Answer 1

是的，根据您的定义（这是正确的），您的算法使用常量或O(1)辅助空间：循环索引，可能需要一些用于设置函数调用本身的常量堆空间等。

确实，可以认为循环索引在输入大小上是位对数的，但它通常被近似为常数。

根据维基百科条目：

在计算复杂性理论中，DSPACE或SPACE是描述确定性图灵机的存储空间资源的计算资源。它表示“正常”物理计算机使用给定算法解决给定计算问题所需的内存空间总量

因此，在“普通”计算机中，索引将被视为每个 64 位，即O(1)。