算法的效率主要由以下两个复杂度来评估：
时间复杂度：评估执行程序所需要的时间。可以估算出程序对处理器的使用程度
空间复杂度：评估执行程序所需要的的存储空间。可以估算出程序对计算机内存的使用程度
设计算法时，一般要先考虑系统环境，然后在权衡时间复杂度和空间复杂度，选取一个平衡点。不过，时间复杂度要比空间复杂度更容易产生问题，因此算法主要研究的也是时间复杂度，不说明的情况下，复杂度指的就是时间复杂度。
下面看一个小栗子：
fun fun1(): Int {
println("哈，我是345")
return 0;
}
fun fun2(n: Int): Int {
for (i in 0..n) {
println("哈，我是345 ")
}
return 0
}
首先，调用一次 fun1，内部会执行两次语句，这个两次可以记做为常数
调用一次 fun 2，内部会执行 1 + (n+1)+n +n +1，也就是 3n +3次，为啥呢，如下：
1，首先 i = 1是一次。
2，i 每次会判断是否小于 n ，会执行 n+1 次。
3，i 每次循环会自增，则执行 n 次。
4，打印语句会执行 n 次
5，return 一次
最终的结果为 3n+3次
所以上面的两个函数的执行次数分别是 2 和 3n+3 次。
但是日常开发中不可能这样去数，所以根据代码执行时间和执行过程就有一个规律，也就是代码执行的时间 T(n) 和代码的执行次数 f(n) ，这个是成正比的，而且这个规律有一个公式 ：
T
(
n
)
=
O
(
f
(
n
)
)
T(n) = O(f(n))
T(n)=O(f(n))
其中，n 是输入数据的大小或者输入数据的数量
T(n) ：表示一段代码的总执行时间
f (n)：表示一段代码的执行总次数
0 ：表示代码的执行时间 T(n) 和执行次数 f(n) 成正比
完整的公式看着有些麻烦，我们平时的算法复杂度主要是用 0() 来表示，读作大欧表示法。
回到上面的两个例子：
上面的写法还是非常麻烦，如果函数的内部的执行次数是固定的，并没有变量存在，那么他的执行时间也就没有什么差别了，例如 O(3) 和 O(4) 。所以复杂度中有一个同意的简化方法，这个简化方法的估算就是我们最终的时间复杂度，简化过程如下：
如果 T(n) = 常数
那么时间复杂度可以估算为 1 ，因此 T(n) = 2 的复杂度就是 1
对于 fun1() 函数，他的执行次数是一个常数，也就是说他的数量是固定的，那么他的时间复杂度就是 O(1)，就算是它内部有上万行代码，时间复杂度也是 0(1)
如果 T(n) = 常数 * n + 常数
可以直接 去掉后面的 + 常数，应为当 (常数 * n) 越来越大，后面的则是保持不变，所以后面的相当于不存在，所以可以直接省略
然后 (常数 * n) 中的常数可以估算为 1，也可以理解为去掉这个作为系数的常数，所以他的时间复杂度就是 0(n)
对于 fun2() 函数，他的执行次数是 常数 *n ，那么他的时间复杂度就是 0(n)
因此 T(n) = 3n + 3 的复杂度为 n
T(n) = 多项式(5n³ + 6666n² + 233)
对于多项式，我们只需要保留 n 的最高次项，也就是保留 n 的次方数最大的那一项，低于这个次项的直接忽略不计。因此 时间复杂度就是 0(n³)
O(1)：常数阶
fun fun1(): Int {
println("哈，我是345")
println("哈，我是345")
println("哈，我是345")
return 0;
}
只要算法中没有循环或者递归，不管多少行代码，他的复杂度都是 0(1)
O(n)：线性阶
fun fun2(n: Int): Int {
for (i in 0..n) {
println("哈，我是345 ")
}
for (i in 1..n) {
println("哈，我是345 ")
}
return 0
}
虽然上面有两个循环，但是并没有嵌套，所以时间复杂度就是 0(n)
O(n²)：平方阶
fun fun2(n: Int): Int {
for (i in 0..n) {
for (i in 1..n) {
println("哈，我是345 ")
}
}
for (i in 1..n) {
println("哈，我是345 ")
}
return 0
}
O(logn)：对数阶
最经典的例子就是二分查找了，每次都从剩下的一半中进行查找，这就是典型的 logn。因为循环的次数影响的主要来源就是 n / 2， 这个时间复杂度就是 O(logn)。
fun foo3(n:Int){
for(let i = 1; i < n; i *= 2){
console.log("一天")
}
}
循环执行的次受到了 i *= 2 影响，乘完后距离 n 就越来越近了。该例子中：
真数，也就是 n 的大小
底数就是值变化的规律，例如这里每次循环都是 i *= 2 ，这个乘2就是规律。例如 1,2,3,4,5 这样的话，底数就是 1，每个数的规律变化都是 +1
对数可以理解为 *2 乘了多少次的次数。
所以，这个题中的 底数就是 2，对数就是 b，结果就是 n ，表达式如下：
a^b = n ，读作以 a 为底 n 的对数等于 b，也就是 2^b = n，读作以2为底n的对数。转换一下，就是 2^b = n
所以这个题就可以理解为 log2n = ?，用时间复杂度就可以表示为 O(log2n)，由于时间复杂度需要去掉系数和常数所以这个时间复杂度就是 O(logn)，
| 复杂度 | 名称 |
|---|---|
| 0(1) | 常数复杂度 |
| 0(logn) | 对数复杂度 |
| O(n) | 线性复杂度 |
| O(n²) | 平方 |
| 0(n³) | 立方 |
| 0(2^n) | 指数 |
| O(n!) | 阶乘 |
以上复杂度都是由快到慢排列
以上数据图片参自https://juejin.cn/post/6999307229752983582
空间复杂度就是算法需要多少内存，占用了多少空间，常用的空间复杂度有 O(1) ,O(n) ,O(n²)，
O(1)
fun fun1(): Int {
println("哈，我是345")
println("哈，我是345")
println("哈，我是345")
return 0;
}
只要不是因为算法的运行而额外的导致空间增长，内部无论多少行代码，空间复杂度都是 O(1)
O(n)
fun fun2(n: Int) {
val list = arrayListOf<Int>()
for (i in 0..n) {
list.add(i)
}
}
如上面这种，n 的数值越大，所需要分配的空间就越多，所以他的空间复杂度是 O(n) ，时间复杂度也是 O(n)
O(n²)
fun fun2(n:Int){
var list = ArrayList<ArrayList<Int>>()
}
这种复杂度一般出现在二位数组，或者是矩阵的情况下。
因为最近在刷一些算法题，恰好对这些有点陌生，所以就复习了一下。
另外，最近一直在刷一些算法题，有兴趣的同学可以一起来刷，每天一到两个小算法，也算是消磨一下时间。地址是：*https://github.com/Blue-knife/Tortoise *，直接看 issus 即可。