算法是指用来操作数据、解决程序问题的一组方法。
一个算法的好坏是由它运行所需要的时间和消耗的空间评定的。
也就是时间维度和空间维度，量化出来就是执行当前算法所消耗的时间（时间复杂`）和执行当前算法所占用的内存空间（空间复杂度）。
时间复杂度
示例代码：
int count(int n){
int sum = 0;
for(int i = 0; i < n; i++){
sum += 1;
}
return sum;
}
假设每一行代码的执行时间都是time，那么
- 第二行执行的时间就是time
- 第三行执行的时间就是n*time
- 第四行执行的时间就是n*time
- 第五行执行的时间就是time
合计执行的总之间是2time+ 2n*time。因此这段代码执行的总时间和每行代码执行的次数成正比！
将算法执行的时间复杂度记为T(n)，使用O表示正比例关系，因此就有：
T(n) = O(2n+2)， 通用公式为T(n) = O(f(n))
这个公式只是监禁时间复杂度公式，只表明代码的执行时间随数据规模增长的变化趋势，简称时间复杂度
当n趋近于无穷大时，常量2和首相系数2以及低阶项可以省略掉，比如一个无穷大+100000000，结果还是无穷大。
因此本算法的时间复杂度为T(n)=O(n)
通过其他实例可发现，同理可得，常见的时间复杂度常量级有：
- 常数阶--O(1)
- 对数阶--O(㏒₂ⁿ)
- 线性阶--O(n)
- 现行对数阶---O(n㏒₂ⁿ)
- 平方阶---O(n²)
- 立方阶---O(n³)
- K次方阶---O(n^k)
- 指数阶---O(2ⁿ)
从上至下，时间复杂度越来越大，执行效率越来越低
1. 常数阶
示例：
int printNum(int i){
int j = 1;
j ++;
return i+j;
}
无论代码执行了多少行，只要没有循环等复杂结构，那么这个代码时间复杂度都是O(1)，假设每行代码执行的时间都是time，代码的行数是有限的即常量级别（实际开发函数中代码不会超过80行，参见阿里巴巴Java开发手册-2020最新嵩山版.pdf，提取码：yxbz），设为常数k，那么执行所花费的时间为k * time，k为常数，因此时间复杂度为常数阶，表示为O(1)
2. 线性阶
实例：
int count(int n){
int sum = 0;
for(int i = 0; i < n; i++){
sum += 1;
}
return sum;
}
见本文开头
3. 对数阶
实例：
int i = 1;
while(i < n){
i = i * 2;
}
本实例中i的值乘以2以后越来越渐进n，终将i >= n的时候退出循环，假设在循环了k次之后i = n，也就是说2 ^ k == n，n = 2 ^ k，即k = ㏒₂ⁿ，即本算法的时间复杂度是O(㏒₂ⁿ)
部分资料对数阶的复杂度写为O(㏒ⁿ)，是有问题的，对数函数只有在地数是e的时候用㏑ⁿ表示
4.线性对数阶
实例：
for(int i = 0; i < n; i++){
i = 1;
while(i < n){
i = i * 2;
}
}
同上
5.平方阶
实例：
int sum = 0;
for(int x = 0; x < n; x++){
for(int j = 0; j < n; j++){
sum = sum +x + j;
}
}
此时的时间复杂度是O(n²)
均摊时间复杂度
ArrayList底层维护了一个数组，因此他的插入时间复杂度是O(1)
假设现在自己实现了一个ArrayList数组，每次空间用尽之后，新建一个新的数组，带下是原来的两倍，使用for将旧数组的数据拷贝到新数组，那么此操作的时间复杂度就是O(n)，每次的拷贝操作都是在进行了n次时间复杂度为O(1)的插入操作之后进行的。那么把O(n)的时间复杂度操作均分到n次O(1)的操作上面，均摊下来几乎所有的插入时间复杂度都是O(1)
空间复杂度
空间复杂度的全称是渐进空间复杂度，表示算法消耗的存储空间和数据规模的增长关系。
通常使用S(n)来表示。
空间复杂度比较常用的有O(1)、O(n)、O(n²)
空间复杂度O(1)
实例：
int i = 1;
int j = 2;
j++;
i++;
int m = i * j;
算法中的变量所分配的空间都不随着处理数据量变化，因此他的空间复杂度S(n) = O(1)
空间复杂度O(n)
实例：
int[] m = new int[n]
for(i=1; i<=n; ++i)
{
j = i;
j++;
}
这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)
文章参考：
- 算法的时间与空间复杂度（一看就懂）
-
一次搞懂时间复杂度和空间复杂度
感谢两位大牛！
