AlexChen's Blog时间复杂度和空间复杂度
时间复杂度
在计算机科学中，算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大 O 符号表述，不包括这个函数的低阶项和首项系数。
这里的大 O 用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。但是我们依然说快速排序是 O(nlogn) 的时间复杂度，这个就是业内的一个默认规定，这里说的 O 代表的就是一般情况，而不是严格的上界。
常见的时间复杂度：
- 常数阶 O(1)
- 对数阶 O(logN)
- 线性阶 O(n)
- 线性对数阶 O(nlogN)
- 平方阶 O(n²)
- 立方阶 O(n³)
- K 次方阶 O(n^k)
- 指数阶 O(2^n)
有时候我们去计算时间复杂度的时候发现不是一个简单的 O(n) 或者 O(n^2)，而是一个复杂的表达式，例如：
O(2*n^2 + 10*n + 1000)O(2*n^2 + 10*n + 1000)那这里如何描述这个算法的时间复杂度呢，一种方法就是简化法。
去掉运行时间中的加法常数项（因为常数项并不会因为 n 的增大而增加计算机的操作次数）。
O(2*n^2 + 10*n)O(2*n^2 + 10*n)去掉常数系数
O(n^2 + n)O(n^2 + n)只保留保留最高项，去掉数量级小一级的 n（因为 n^2 的数据规模远大于 n），最终简化为：
O(n^2)O(n^2)如果这一步理解有困难，那也可以做提取 n 的操作，变成 O(n(n+1)) ，省略加法常数项后也就别变成了：
O(n^2)O(n^2)所以最后我们说：这个算法的算法时间复杂度是 O(n^2) 。
空间复杂度
在计算机科学中，一个算法或程序的空间复杂度定性地描述该算法或程序运行所需要的存储空间大小。空间复杂度是相应计算问题的输入值的长度的函数，它表示一个算法完全执行所需要的存储空间大小。
常见的空间复杂度：
常数阶 O(1)
线性阶 O(n)
平方阶 O(n²)