空间复杂度的四种计算情况，超级简单好懂-白红宇的个人博客

发布日期：2021-05-08 01:39:57 浏览次数：21 分类：精选文章

本文共 350 字，大约阅读时间需要 1 分钟。

刚接触空间复杂度的时候，可能很多人知道什么是空间复杂度，但是往往不知道怎么计算。

和时间复杂度类似，空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，也是使用大O表示法。

1、常量空间

存储空间大小固定，和输入没有关系时，空间复杂度是O(1)

2、线性空间

算法中定义了一个线性集合，如一个列表，并且集合大小和输入规模n成正比，空间复杂度记为O(n)

3、二维空间

算法中定义了一个二维列表集合，并且集合的长和宽都和输入规模n成正比，空间复杂度记为O(nn)/O（nm)

4、递归空间

递归过程就是一个进栈和出栈的过程，当进入一个新函数时，进行入栈操作，把调用的函数和参数信息压入栈中；当函数返回时，执行出栈。

递归的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是O(n)。

上一篇：十大排序算法之二：选择排序(Python)

下一篇：排序算法总结

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！