algorithm - 如何计算函数的空间复杂度？

Question

我的基本理解是如果我有这样的功能:

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

参数需要 3 个空间单位，局部变量需要 1 个空间，而且这永远不会改变，所以这是 O(1) .

但是如果我有这样一个函数呢:

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

a 需要 N 个单元, M 单位为 b和 L 单位为 c和 1 个单位 i和 n .所以它需要 N+M+L+1+1存储量。

那么这里空间复杂度的大 O 是什么？那个占用内存大？IE。如果 N 比 M 和 L 占用更高的内存(从更高的意思假设大于 10**6 ) - 那么可以安全地说空间复杂度是 O(N)或者不像我们在时间复杂度方面所做的那样？

但如果所有三个，即 a、b、c 都没有太大差异

喜欢这个功能

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];
        }
    }
}

那么空间复杂度是多少？ O(N+M+L) ？还是最大的那个？

Answer 1

当我们谈论空间复杂度时，我们不会考虑输入使用的空间。

这让我们可以讨论常量空间、O(log n) 空间等算法。如果我们开始计算输入，那么所有算法都至少是线性空间!

空间复杂度的标准多带图灵机定义也不计算输出。

输入是只读的，输出是只写的，不计入空间复杂度。

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.