Space 嵌套循环的复杂度

Question

我对 space 算法的复杂性感到困惑。理论上，它对应于算法使用的额外堆栈 space，即输入以外的堆栈。但是，我有问题指出，这到底是什么意思。

例如，如果我有以下暴力算法来检查数组中是否没有重复项，这是否意味着它使用 O(1) 额外存储 spaces，因为它使用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)，辅助 space：循环索引，可能一些常量堆 space 需要设置函数调用本身，等等

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

根据 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

因此，在 "normal" 计算机中，每个索引将被视为 64 位，或者 O(1).

Answer 2

这是否意味着它使用 O(1) 额外存储空间 spaces，因为它使用 int j 和 int k？

是.

额外存储space 意味着space 用于除输入本身之外的其他东西。而且，正如时间复杂度一样，如果额外的 space 不依赖于 （当输入大小增加时增加）对输入大小本身的大小，那么 space 复杂度为 O(1)

Answer 3

是的，你的算法确实是 O(1) 存储 space ¹，因为你使用的辅助 space 有一个严格的上限与输入无关。

(1) 假设用于迭代的整数在限制范围内，通常最多为 2^32-1

Space 嵌套循环的复杂度

Space complexity of nested loop

algorithm

space-complexity