嵌套循环的空间复杂性

当涉及算法的空间复杂性时，我感到困惑。 理论上，它对应于算法使用的额外堆栈空间，即输入以外的其他堆栈空间。 然而，我有问题指出，究竟是什么意思。

例如，如果我有一个下面的蛮力算法来检查数组中是否有重复项，这是否意味着它使用了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;
            }
        }
    }
}

---

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

的确，可以认为循环索引是输入大小的比特对数，但通常近似为常数。

根据维基百科条目：

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

因此，在“普通”计算机中，索引将被认为是64位，即O（1）。

---

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

是的 。

---

额外的存储空间意味着用于输入本身之外的东西的空间。 而且，就像时间复杂性起作用一样，如果这个额外空间不依赖于输入大小增加时的增加量，那么空间复杂度就是O(1)

---

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

（1）假定用于迭代的整数处于受限的范围内，通常最高为2 ^ 32-1

链接地址: http://www.djcxy.com/p/40057.html

上一篇: Space complexity of nested loop

下一篇: How does merge sort have space complexity O(n) for worst case?