一、说明
时间复杂度和空间复杂度是用来评价算法效率高低的2个标准，身为开发者肯定会经常会听到这2个概念，但它们分别是什么意思呢?
其实这两个概念从字面意思上也能看出一二：
- 时间复杂度：就是说执行算法需要消耗的时间长短，越快越好。比如你在电脑上打开计算器，如果一个普通的运算要消耗1分钟时间，那谁还会用它呢，还不如自己口算呢。
- 空间复杂度：就是说执行当前算法需要消耗的存储空间大小，也是越少越好。本来计算机的存储资源就是有限的，如果你的算法总是需要耗费很大的存储空间，这样也会给机器带来很大的负担。
二、时间复杂度的计算
表示方法
常见的时间复杂度量级
- 常数阶O(1)
- 线性阶O(n)
- 对数阶O(logN)
- 线性对数阶O(nlogN)
- 平方阶O(n²)
- 立方阶O(n³)
- K次方阶O(n^k)
- 指数阶(2^n)
接下来再看一下不同的复杂度所对应的算法类型。
常数阶O(1)
int a = 1; int b = 2; int c = 3; 线性阶O(n)
for(i = 1; i <= n; i++) {
j = i; j++; } 对数阶O(logN)
int i = 1; while(i < n) {
i = i * 2; } 可以看到每次循环的时候 i 都会乘2，那么总共循环的次数就是log2n，因此这个代码的时间复杂度为O(logn)。
这儿有个问题，为什么明明应该是O(log2n）,却要写成O(logn)呢？
其实这里的底数对于研究程序运行效率不重要，写代码时要考虑的是数据规模n对程序运行效率的影响，常数部分则忽略，同样的，如果不同时间复杂度的倍数关系为常数，那也可以近似认为两者为同一量级的时间复杂度。
线性对数阶O(nlogN)
for(m = 1; m < n; m++) {
i = 1; while(i < n) {
i = i * 2; } } 线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。
平方阶O(n²)
for(x = 1; i <= n; x++){
for(i = 1; i <= n; i++) {
j = i; j++; } } 把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。
立方阶O(n³)、K次方阶O(n^k)
参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似。
三、空间复杂度计算
空间复杂度 O(1)
如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)。
int i = 1; int j = 2; ++i; j++; int m = i + j; 代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)。
空间复杂度 O(n)
int[] m = new int[n] for(i = 1; i <= n; ++i) {
j = i; j++; } 这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，后面虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)。
总结
评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。可能有的开发者接触时间复杂度和空间复杂度的优化不太多（尤其是客户端），但在服务端的应用是比较广泛的，在巨大并发量的情况下，小部分时间复杂度或空间复杂度上的优化都能带来巨大的性能提升，是非常有必要了解的。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/199791.html原文链接：https://javaforall.net
