漫画算法:小灰的算法之旅学习 – 第1章 算法概述（空间复杂度？）

这是我参与更文挑战的第22天，活动详情查看： 更文挑战

• 紧跟上篇，这篇主要是空间复杂度及相关

什么是空间复杂度

• 简单来说,时间复杂度是执行算法的时间成本,空问复杂度是执行算法的空间成本
• 在运行一段程序时，我们不仅要执行各种运算指令，同时也会根据需要，存储 一些临时的中间数据，以便后续指令可以更方便地继续执行。
• 是对一个算法在运行过程中临时占用存储空间的度量，一个算法在计算机存储器上所占用的存储空间包括存储算法本身所占用的空间，算数和输入输出所占用的存储空间以及临时占用存储空间三个部分，算法的输入输出数据所占用的存储空间是由待解决的问题来决定的，通过参数表由调用函数而来，它随本算法的不同而改变，存储算法本身所占用的存储空间有算法的书写长短成正比。算法在运行过程中占用的临时空间由不同的算法决定。

内存空间是有限的，在时间复杂度相同的情况下，算法占用的内存空间 自然是越小越好。如何描述一个算法占用的内存空间的大小呢?这就用到了算法的 另一个重要指标——空间复杂度(space complexity)

• 和时间复杂度类似，空间复杂度是对一个算法在运行过程中临时占用存储空间 大小的量度，它同样使用了大O表示法。
• 程序占用空间大小的计算公式记作S(n)=O(f(n))，其中n为问题的规模，f(n)为 算法所占存储空间的函数。

空间复杂度的计算

• 常见的空间复杂度有下面几种情形
  • 1. 常量空间
  • 当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记 作O(1)。例如下面这段程序:

 function fun1(){
   let num = 3;
 }
复制代码

2. 线性空间

• 当算法分配的空间是一个线性的集合(如数组)，并且集合大小和输入规模n成正比时，空间复杂度记作O(n)。
  • 例如下面这段程序:

function fun2(n){
   var arr = new Array(n);
 }
复制代码

3、二维空间

• 当算法分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模n 成正比时，空间复杂度记作O(n2)。

function fun3(n){
   var myarr = new Array(n); //先声明一维 
        for ( var i = 0; i < n; i++) { //
            myarr[i] = new Array(); //再声明二维 
            for ( var j = 0; j < n; j++) { //二
                myarr[i][j] = i + j; // 赋值，每个数组元素的值为i+j
            }
        }
复制代码

1. 递归空间

• 递归是一个比较特殊的场景。虽然递归代码中并没有显式地声明变量或集合， 但是计算机在执行程序时，会专门分配一块内存，用来存储“方法调用栈”。