“空间复杂性”是什么意思？

空间复杂性： 空间复杂性这个术语在许多地方被误用为辅助空间。以下是辅助空间和空间复杂性的正确定义。

辅助空间 是算法使用的额外空间或临时空间。

空间复杂性 算法的总空间是算法相对于输入大小占用的总空间。空间复杂性包括辅助空间和输入使用的空间。

例如，如果我们想在空间的基础上比较标准排序算法，那么辅助空间将是比空间复杂度更好的标准。合并排序使用O（n）辅助空间，插入排序和堆排序使用O（1）辅助空间。所有这些排序算法的空间复杂度都是O（n）。

空间复杂性是与时间复杂性平行的概念。如果我们需要创建一个大小为n的数组，这将需要O（n）空间。如果我们创建一个大小为n*n的二维数组，这将需要O（n ^2. )空间。

在递归调用中，堆栈空间也很重要。

例子：

int add (int n){    if (n <= 0){        return 0;    }    return n + add (n-1);}Here each call add a level to the stack :1.  add(4)2.    -> add(3)3.      -> add(2)4.        -> add(1)5.          -> add(0)Each of these calls is added to call stack and takes up actual memory.So it takes O(n) space.

然而，仅仅因为总共有n个调用，并不意味着需要O（n）个空间。

请看下面的函数：

int addSequence (int n){    int sum = 0;    for (int i = 0; i < n; i++){        sum += pairSum(i, i+1);    }    return sum;}int pairSum(int x, int y){    return x + y;}There will be roughly O(n) calls to pairSum. However, those calls do not exist simultaneously on the call stack,so you only need O(1) space.

注： 需要指出的是，空间复杂性取决于多种因素，比如编程语言、编译器，甚至是运行算法的机器。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。