How to calculate the space complexity of function?

I understood the basic that if I have a function like this:

int sum(int x, int y, int z) {
  int r = x + y + z;
  return r;
}

it requires 3 units of space for the parameters and 1 for the local variable, and this never changes, so this is O(1) .

But what if I have a function like this:

void add(int a[], int b[], int c[], int n) {
    for (int i = 0; i < n; ++i) {
        c[i] = a[i] + b[0]
    }
}

Which requires N units for a , M units for b and L units for c and 1 unit for i and n . So it will need N+M+L+1+1 amount of storage.

So what will the big-O for space complexity here? The one which takes higher memory? Ie if N takes more higher momery than M and L (from much higher means suppose larger than 10**6 ) - so is it safe to say space complexity is O(N) or not like we do for time complexity ?

But if all three ie a, b, c are not very much different

Like this function

void multiply(int a[], int b[], int c[][], int n) { 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            c[i] = a[i] + b[j];
        }
    }
}

Then what will be the space complexity? O(N+M+L) ? Or still the biggest one?

---

The space complexity of an algorithm or data structure is the maximum amount of space used at any one time, ignoring the space used by the input to the algorithm. Therefore space complexity of all three examples in your question is O(1)

---

When we talk about space complexity, we don't consider the space used by the input.

This allows us to talk about algorithms which are constant space, O(log n) space etc. If we started counting the input, then all algorithms will be at least linear space!

The standard multi-tape Turing machine definition of space complexity also does not count the output.

The input is read only and output is write only and do not count towards the space complexity.

So to answer your question: look for what memory your method allocates, including stack space for recursion/local variables etc, and that will determine the space complexity.

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

上一篇: 从库中退出（）可以被抛出异常替换？

下一篇: 如何计算函数的空间复杂度？