如何计算函数的空间复杂度？
我明白了如果我有这样的功能的基本：
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]
}
}
这需要N个单位的a ，M单位的b和L单位的c和1单位的i和n 。 所以它需要N+M+L+1+1的存储量。
那么在这里空间复杂性的大O会是什么？ 需要更高内存的那个？ 也就是说，如果N需要比M和L更高的Momery（来自更高的意思是假设大于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) ？ 还是最大的？
算法或数据结构的空间复杂度是任何时候使用的最大空间量，忽略算法输入使用的空间。 因此，你的问题中所有三个例子的空间复杂性是O（1）
当我们谈论空间复杂性时，我们不考虑输入使用的空间。
这使我们可以谈论恒定空间，O（log n）空间等算法。如果我们开始计算输入，那么所有算法都至少是线性空间！
标准的多磁带图灵机定义的空间复杂度也不计算输出。
输入是只读的，输出是只写的，不计入空间复杂度。
所以要回答你的问题：寻找你的方法分配的内存，包括递归/局部变量的堆栈空间等，这将决定空间的复杂性。
链接地址: http://www.djcxy.com/p/26121.html