咱们聊聊数据结构里最基础也最核心的知识点——时间复杂度和空间复杂度，不管是刷题、面试还是平时做项目，搞懂这两个概念都特别关键，它能帮我们快速看出算法好不好用，写出更省事、更高效的代码。很多新手刚接触时总觉得这两个概念很抽象，但只要结合具体例子拆解开来看，就会发现其实一点都不难，今天我就用最直白的方式，带大家彻底搞懂常见的时间复杂度和空间复杂度。
大家要清楚一个关键：算法好用不好用，主要看时间复杂度和空间复杂度这两个方面，时间复杂度管的是算法执行要花多久，空间复杂度管的是算法运行时额外要占多少存储空间，这两者一起决定了算法的好坏，平时做项目时我们常常要在这两者之间选一个平衡点，但前提是我们得先学会怎么分析它们。
时间复杂度
时间复杂度全称是渐进时间复杂度，它描述的是算法执行时间随着输入规模n的变化而变化的趋势，不是具体要花多少时间，因为算法实际跑多久会受电脑配置、所用编程语言、数据排列情况等多种因素影响，没法精确算出来，而时间复杂度能帮我们抛开这些没用的干扰，只关注算法本身好不好用。我们一般用大O符号（O）来表示时间复杂度，它反映的是最坏情况下算法执行时间的最大值。
分析时间复杂度有个关键原则：不用管常数项和那些增长慢的项，只留下增长最快的那一项就好。比如说一个算法要执行3n+5次操作，我们就忽略常数5和系数3，把它的时间复杂度记成O(n)；再比如n²+2n+3，里面增长最快的是n²，所以这个算法的时间复杂度就是O(n²)。下面我就一个个给大家讲几种常见的时间复杂度，按好用程度从高到低来说。
1. O(1)：常数时间复杂度
这是最好用的一种时间复杂度，意思是算法执行时间不会随着输入规模n的变化而改变，不管n是10、1000还是10000，算法要做的操作次数始终是固定的。
最典型的例子就是访问数组和交换变量，比如我们要交换两个变量的值，只要定义一个临时变量，做三次赋值操作就够了，不管这两个变量的数值是什么、输入规模有多大，操作次数都不会变；再比如访问数组的第k个元素，直接用下标定位，一步就能完成，这也属于O(1)复杂度。这种算法特别好用，平时开发时只要能用，就优先用。
2. O(log n)：对数时间复杂度
这种复杂度的好用程度仅次于O(1)，它的关键特点是每次执行操作都会把问题规模缩小一半，操作次数随着n的增长呈对数趋势变化，这里的对数默认以2为底，因为大多数算法都会用二分的方式缩小问题规模。
最经典的例子就是二分查找，假设我们有一个排好序的数组，想找到某个目标值，二分查找的思路就是每次取数组中间的元素和目标值对比，如果中间值比目标值大，就只在左边一半继续找，如果中间值比目标值小，就只在右边一半继续找，每次都把查找范围缩小一半。比如n=8时，最多找3次（2³=8），n=16时最多找4次，操作次数是log₂n，所以它的时间复杂度是O(log n)。除了二分查找，平衡二叉树的插入、删除、查找等操作，也都是O(log n)复杂度。
3. O(n)：线性时间复杂度
这种复杂度就是算法的操作次数和输入规模n成正比，n扩大几倍，操作次数就跟着增加几倍，是平时开发中最常见的一种复杂度。
典型的例子就是遍历数组和线性查找，比如我们要遍历一个长度为n的数组，把每个元素都打印出来，就需要做n次打印操作；再比如线性查找，要在一个没排好序的数组里找目标值，最坏的情况下要把整个数组都遍历一遍，做n次对比操作，这两种情况的时间复杂度都是O(n)。这种算法好用程度一般，适合处理数据量小的情况，要是n很大，效率就会明显变差。
4. O(n log n)：线性对数时间复杂度
这种复杂度是O(n)和O(log n)结合起来的，操作次数是n乘以log n，好用程度在O(n)和O(n²)之间，很多高效的排序算法都是这种复杂度。
最常见的例子就是归并排序、快速排序（平均情况），拿归并排序来说，它的核心思路是分治，先把数组分成两个子数组，分别把这两个子数组排好序，再把排好序的两个子数组合并成一个有序数组。拆分的时候每次都把数组减半，时间复杂度是O(log n)，合并的时候要遍历两个子数组，时间复杂度是O(n)，所以整体时间复杂度就是O(n log n)。这种复杂度处理大数据量时，比O(n²)好用多了，是平时开发中常用的高效算法复杂度。
5. O(n²)：平方时间复杂度
这种复杂度就是算法的操作次数和输入规模n的平方成正比，n扩大几倍，操作次数就扩大几倍的平方，好用程度比较低，只适合处理数据量小的情况。
典型的例子就是嵌套循环，比如冒泡排序、选择排序，拿冒泡排序来说，外层循环要执行n次，每次外层循环执行时，内层循环都要执行n-i次（i是外层循环的次数），整体操作次数大概是n(n-1)/2，忽略那些增长慢的项和常数项后，它的时间复杂度就是O(n²)。再比如一个双层for循环，外层循环执行n次，内层循环也执行n次，总共要做n²次操作，这也属于O(n²)复杂度。要是n很大，这种算法会跑很久，平时开发中尽量不用。
6. 其他低效复杂度
除了上面几种常见的，还有O(n³)、O(2ⁿ)、O(n!)等不好用的复杂度，这类复杂度的算法执行时间会随着n的增长快速上升，通常只能处理数据量小的情况或者特殊场景。比如O(2ⁿ)常见于没优化过的递归斐波那契数列，n=20时，操作次数就有一百万次；O(n!)常见于旅行商问题的暴力解法，n=10时，操作次数就有3628800次，基本没什么实际用处。
空间复杂度
空间复杂度和时间复杂度差不多，也是用大O符号表示，它衡量的是算法执行时额外需要的存储空间随着输入规模n的变化趋势，这里要注意，输入数据本身占的空间不算，我们只看算法执行时额外开辟的空间，比如临时变量、递归调用栈、新创建的数据结构等。
分析空间复杂度比时间复杂度简单，关键就是看算法额外开辟的空间会不会随着n的变化而变化，下面我就给大家讲几种常见的空间复杂度。
1. O(1)：常数空间复杂度
这种复杂度就是算法执行时需要的额外空间是固定的，不会随着输入规模n的变化而改变，和O(1)时间复杂度一样，是最好用的空间复杂度。
典型的例子就是交换变量、原地排序（比如冒泡排序），比如交换两个变量的值，只要一个临时变量就够了，不管n多大，临时变量的数量都不变；再比如冒泡排序，只需要几个临时变量存中间值，不用额外开辟数组之类的空间，所以它的空间复杂度是O(1)。这种算法不占额外空间，平时开发时优先考虑。
2. O(n)：线性空间复杂度
这种复杂度就是算法需要的额外空间和输入规模n成正比，n扩大几倍，额外空间就跟着扩大几倍。
常见的例子有创建长度为n的数组、递归调用栈（非尾递归）、哈希表缓存，比如我们创建一个长度为n的数组存数据，数组的空间会随着n的增大而增大，它的空间复杂度就是O(n)；再比如递归版斐波那契数列，每次递归都会在栈里开辟新空间，递归深度是n，所以栈空间的复杂度是O(n)；另外，用哈希表存n个数据，哈希表的空间也会随着n线性增长，这也属于O(n)复杂度。
3. O(n²)：平方空间复杂度
这种复杂度就是算法需要的额外空间和输入规模n的平方成正比，通常出现在需要创建二维数据结构的场景中，好用程度比较低。
典型的例子有创建n×n的二维数组、动态规划中的二维dp表，比如我们创建一个n行n列的二维数组存数据，数组的元素个数是n²，额外空间随着n²增长，它的空间复杂度就是O(n²)；再比如用动态规划解决最长公共子序列问题，需要创建一个n×m的二维dp表（n和m是两个字符串的长度），当n和m差不多大时，空间复杂度就接近O(n²)。这种算法占的空间比较多，用的时候要多注意。
4. O(log n)：对数空间复杂度
这种复杂度不常见，主要出现在分治算法中，额外空间随着n的对数增长，比如递归版二分查找，递归调用的深度是log n，栈空间的占用量随着log n增长，所以它的空间复杂度是O(log n)。这种复杂度很好用，好用程度在O(1)和O(n)之间。
复杂度分析的核心要点
最后我给大家总结几个分析复杂度的小技巧，帮大家快速学会：
- 分析时间复杂度主要看循环和递归，单层循环一般是O(n)，双层嵌套循环一般是O(n²)，递归就看调用深度，二分类型的递归一般是O(log n)；
- 分析空间复杂度主要看额外开辟的空间，只需要关注临时变量、新创建的数据结构、递归栈，输入数据本身占的空间不用算；
- 不用关注无关的细节，不管是时间还是空间复杂度，都可以忽略常数项和增长慢的项，只留下增长最快的那一项；
- 时间和空间可以互相换，很多时候我们可以多占点空间来节省时间（比如用哈希表存数据，用O(n)的空间换O(1)的查找时间），也可以多花点时间来节省空间（比如原地排序，用O(1)的空间换O(n²)的时间），具体怎么选看实际需求。
总结
时间复杂度和空间复杂度是数据结构和算法的基础，也是面试时常考的知识点，掌握常见的复杂度类型，能帮我们快速判断算法好不好用，在刷题和开发时做出更合适的选择。其实核心很简单：时间复杂度看操作次数的增长趋势，空间复杂度看额外空间的增长趋势，结合例子多分析、多练习，很快就能熟练掌握。