一篇文章帮你搞定时间复杂度、空间复杂度！！！

引言在数据结构中我们常常会用到时间复杂度和空间复杂度不仅在日常学习中要用到面试的时候也会问道我们要足够清晰了解这两个概念并且能够计算出对应算法题的时间复杂度和空间复杂度这两者较为重要的是时间复杂度因为空间复杂度相对于公司来说可以扩大磁盘空间但时间复杂度就不一样了。所以一般都会要求牺牲空间复杂度来降低时间复杂度不仅在公司是这样我们在刷算法题的时候也要注重时间复杂度时间复杂度1.定义也可以理解为算法的执行效率是算法执行时间与算法输入值的关系用大O表示法只保留最高阶项忽略常数和低阶。2.常见时间复杂度O(1)执行次数固定一般没有循环例如简单赋值、取数组的第一个元素O(log n)对数时间每次把问题规模减半例如二分查找O(n)线性时间一般是循环例如for循环遍历数组元素O(n log n)线性对数一般是数组排序例如外层是循环n内层是lognO(n2)平方时间两层嵌套循环例如冒泡排序、简单选择排序O(2ⁿ)、O(n!):指数 / 阶乘很少会用到因为效率太低了3.对比从上到下依次增大空间复杂度1.定义算法存储空间与输入值之间的关系也就是输入值要占用多少内存2.常见空间复杂度O(1)只用固定几个变量不随 n 变化。例原地交换、简单计算。O(n)开了一个长度为 n 的数组 / 列表。例用数组存中间结果。O(log n)递归深度是 log n。例二分递归。O(n²)开二维数组 n×n。总结时间复杂度看执行次数随 n 怎么涨空间复杂度看额外内存随 n 怎么涨只关心最高阶O(2n3) O(n)O(n²n) O(n²)