算法的空间复杂度

要计算算法中的空间复杂度实际上就是计算算法占用内存的大小！要计算占用内存空间的大小，我们就要知道算法中有多少变量，每种变量对应了多少内存空间！虽然PHP是弱类型的语言，但不代表PHP没有类型！

所以，PHP每种数据类型占用的实际内存大小也不相同，不过我们在计算空间复杂度时，这些具体的值都会被简化掉！要研究PHP数据类型的大小需要阅读PHP内核代码，这里不是我们的重点，相关的内容我们制作专门的文章来说明。

在这里就那我们最好理解的形式来计算，按照标准C语言的类型大小就好了。

我们就以上面的两个代码片段为例打造一个遍历数组元素的算法来计算空间复杂度。

由于内存空间会受到所在机器及计算机系统影响，这里假设是在64位下的linux系统环境下的数据。

function arrIterator( $arr ){ {1}
    for( $i=0; $i < count( $arr ); $i ++ ){ {2}
    	echo $arr[ $i ]; {3}
    }
}

第一步：统计算法中变量的个数，类型和对应的内存数量:

分析代码可知，其中用到的变量如下：
$arr 数组 存储有n个整型元素
$i 整型

第二步：计算算法总内存空间f(n):

f(n) = n * 8 + 8 = 8*n + 8

第三步：计算时间复杂度T(n):

S(n) = O( f(n) ) = O( 8*n + 8 )
即
S(n) = O( 8*n + 8 )

第四步：简化
简化方法和时间复杂度相同:

S(n) = O(n)

function arrIterator( $arr ){ {1}
    $len = count( $arr ); {2}
    for( $i=0; $i < $len; $i ++ ){ {3}
        echo $arr[ $i ]; {4}
    }
}

第一步：统计算法中变量的个数，类型和对应的内存数量:

分析代码可知，其中用到的变量如下：
$arr 数组 存储有n个整型元素
$len 整型
$i 整型

第二步：计算算法总内存空间f(n):

f(n) = n * 8 + 8 + 8 = 8*n + 16

第三步：计算时间复杂度T(n):

S(n) = O( f(n) ) = O( 8*n + 16 )
即
S(n) = O( 8*n + 16 )

第四步：简化

S(n) = O(n)

通过比较两种实现方式的空间复杂度都是O(n)级别的，但是第二种方案使用了代码片段二优化之后反而空间复杂度比使用第一个代码片段增加了整型数据的大小，但是我们公认为第二种更快了！而其中原因就是用空间换取了时间！

李斌