算法的空间复杂度

原文：https://www.studytonight.com/data-structures/space-complexity-of-algorithms

每当一个问题的解决方案被写入时，需要一些内存来完成。对于任何算法，存储器可用于以下目的:

  1. 变量(包括常量值、临时值)
  2. 程序指令
  3. 执行

*空间复杂度是算法执行和产生结果所使用的内存量(包括算法的输入值)。*

有时候辅助空间会和空间复杂度混淆。但是辅助空间是算法在执行过程中使用的额外空间或临时空间。

空间复杂度 = 辅助空间+输入空间

执行时的内存使用

执行时，算法使用内存空间有三个原因:

  1. Instruction Space

    这是用于保存指令编译版本的内存量。

  2. Environmental Stack

    有时一个算法(函数)可能在另一个算法(函数)内部被调用。在这种情况下，当前变量被推到系统栈上，等待进一步执行，然后调用内部算法(函数)。

    例如，如果一个函数A()在其内部调用函数B()，那么函数A()的所有变量将被暂时存储在系统栈上，而函数B()在函数A()内部被调用和执行。

  3. Data Space

    变量和常量使用的空间量。

但是在计算任何算法的空间复杂度时，我们通常只考虑数据空间，而忽略了指令空间和环境栈。

计算空间复杂度

为了计算空间复杂度，我们需要知道不同类型的数据类型变量所使用的内存值，这通常因不同的操作系统而异，但是计算空间复杂度的方法保持不变。

| 类型 | 大小 | | bool，char，无符号字符，有符号字符，int8 | 1 字节 | | int16，短，无符号短，wchar_t，wchar_t | 2 字节 | | float，int32，int，无符号 int，long，无符号 long | 4 字节 | | double，__int64，long double，long long | 8 字节 |

现在让我们通过几个例子来学习如何计算空间复杂度:

{
    int z = a + b + c;
    return(z);
}

在上面的表达式中，变量a、b、c和z都是整数类型，因此它们将各占用 4 个字节，因此总内存需求为(4(4) + 4) = 20 bytes，这额外的 4 个字节用于返回值。并且因为这个空间需求对于上面的例子是固定的，因此它被称为恒定空间复杂度。

我们再举一个例子，这次有点复杂，

// n is the length of array a[]
int sum(int a[], int n)
{
    int x = 0;        // 4 bytes for x
    for(int i = 0; i < n; i++)    // 4 bytes for i
    {    
        x  = x + a[i];        
    }
    return(x);
}
  • 在上面的代码中，数组a[]元素需要4*n字节的空间。
  • x、n、i和返回值各 4 个字节。

因此，总内存需求为(4n + 12)，随着输入值n的增加而线性增加，因此称为线性空间复杂度。

类似地，随着算法复杂度的增加，我们也可以有二次和其他复杂的空间复杂度。

但是我们应该始终专注于以保持空间复杂度最小的方式编写算法代码。