您当前的位置： 首页 > 学无止境 > 心得笔记 网站首页心得笔记

一个视频教会你算法的空间复杂度

发布时间：2020-10-07 17:03:20编辑：雪饮阅读（）

之前我们了解了算法的时间复杂度，让我们来回忆下该定义：

输入值、算法的执行时间、数据规模之间的关系

那么接下来我们来了解下算法的空间复杂度。

算法的空间复杂度

定义：算法所使用的存储空间与输入值之间的关系

算法空间复杂度表示法也同样用大O表示法。

O(1)示例：

def test(num);

       total = 0

       for i in range(num);

              total += i;

       return total

这里实际用到的空间就是total空间，没有其它空间(仅常量)，且total定长为4字节（int），所以该空间复杂度就是O(1)

O(n)示例：

def test(num);

       array = []

       for num in range(nums);

              array.append(num)

       return array

虽然这里实际用到的空间仍旧只有一个array，没有其它空间，但是这里array并非定长，会随着nums正相关，所以该空间复杂度就是O(n)