algorithm - 嵌套循环的空间复杂度

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) 辅助空间:循环索引，可能需要一些常量堆空间来设置函数调用自身等

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

根据Wikipedia entry :

In computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a given algorithm

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