空间复杂度可以理解为一段程序在内存空间分配了多少，程序使用了多少空间或者内存规模。相比时间复杂度，空间复杂度非常简单直观。空间复杂度主要通过两个特征来把握
1. 数组的长度
2. 使用了递归，看递归的深度。递归深度就是其空间复杂度
递归若结合了数组的使用。则看二者谁占用的空间最大，取最大值为空间复杂度。一般我们认为最坏发生的可能结果才是最终的结果。
举例：使用了数组，在内存中分配了一段连续的存储空间。传入的元素个数，就是程序的空间复杂度。
o （n）空间复杂度
例子中，我存入了int 类型的5个元素，最后得到这个数组n的长度就是5. 这5个元素在内存中就是一段连续的存储空间。所以空间复杂度o（n）。 n代表元素有多少，就分配多少内存。不多不少。
借用LeetCode 70 爬楼梯，来判定程序空间复杂度
题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。
示例 1：当 n = 2 ；答案：两种方法。
解释： 第1种方法：1 阶 + 1 阶 ；第2种方法：直接爬2 阶。所以共两种方法
示例 2：当n = 3 ； 答案：三种方法。
解释： 有三种方法可以爬到楼顶。
方法1： 1 阶 + 1 阶 + 1 阶；
方法2：1 阶 + 2 阶 ；
方法3：2 阶 + 1 阶。
思路一: 递归
递归思想
爬楼梯问题实质是斐波那契数列。很自然想到递归来实现：
想求抵达第n层的方法，取决于（n-1）层和（n-2）层方法之和。因为当爬到第n-1层或者第n-2层，根据题目所述，下一步都会是第n层。（因为一步一步爬，也可以一次爬两层）；同理，n-1层取决于n-2，n-3... 以此类推
可是，递归构建的树形结构，所有左边分支都是层数减1， 右边分支都是层数-2。 生成了大量重复节点的计算，且递归的深度是n层。 由下图可以看到。每一个f() 占据一个内存空间，层层嵌套，直至满足递归的退出条件，n==0 or n==1 （return 1）。所以，用递归来解决爬楼梯问题，空间复杂度非常高。o（n）
递归
思路二：动态规划法
动态规划思路
动态规划算法的核心思想是自底向上的分析问题，先着眼于小问题，才能解决大问题。可以参考代码的注释。例子中，所有的爬楼梯第n层方法，都是从爬一层和爬两层的方法数之和算起。
总结：用动态规划法，我们只是定义了first，second，third变量。并没有引入数组，开辟内存空间存放数据。也没有递归函数的出现。一层循环，所以时间复杂度是O（n）；空间复杂度是O(1) 常量级内存空间。
网友评论