Space complexity of nested loop

I am confused when it comes to space complexity of an algorithm. In theory, it corresponds to extra stack space that an algorithm uses ie other than the input. However, I have problems pointing out, what exactly is meant by that.

If, for instance, I have a following brute force algorithm that checks whether there are no duplicates in the array, would that mean that it uses O(1) extra storage spaces, because it uses int j and 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;
            }
        }
    }
}

---

Yes, according to your definition (which is correct), your algorithm uses constant, or O(1), auxilliary space: the loop indices, possibly some constant heap space needed to set up the function call itself, etc.

It is true that it could be argued that the loop indices are bit-logarithmic in the size of the input, but it is usually approximated as being constant.

According to the 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

So, in a "normal" computer, the indices would be considered each to be 64 bits, or O(1).

---

would that mean that it uses O(1) extra storage spaces, because it uses int j and int k?

Yes .

---

Extra storage space means space used for something other then the input itself. And, just as time complexity works, if that extra space is not dependent (increases when input size is increased) on the size of the input size itself, then the space complexity would be O(1)

---

Yes, your algorithm is indeed O(1) storage space 1, since the auxillary space you use has a strict upper bound that is independent on the input.

(1) Assuming integers used for iteration are in restricted range, usually up to 2^32-1

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

上一篇: 空间差异不同排序算法的复杂性

下一篇: 嵌套循环的空间复杂性