2.时间复杂度和空间复杂度
1.算法好坏的度量方法
- 事后统计方法：用设计好的测试程序和数据，对完成的算法进行测试，从而确定算法效率的高低
- 事先分析估算方法：在实现算法之前，使用事先统计方法对算法进行估算
考虑到成本和不同机器的差异，我们在解决问题选取一个算法时，一般采用事先分析估算方法
2. 事先分析估算的衡量标准
我们如何事先来衡量一个算法的好坏呢？当然是既要马儿跑得快，又要马儿吃得少
可以从下面两个方面来衡量：
- 时间复杂度：跑得快，就是算法效率的体现，对于同一规模的输入，处理的时间越快，算法越好
- 空间复杂度：吃得少，就是算法开销的体现，对于同一规模的输入，算法所需存储空间的开销越低，算法越好
总结：使用时间复杂度和空间复杂度来事先评判一个算法的好坏
3. 时间复杂度
3.1 定义
时间复杂度就是用来衡量程序随着输入规模的增大，程序需要执行时间的增长规模。我们关注的是增长的量级，而不是具体的运行时间。
我们用下面的表达式来表示程序运行时间T(n)关于程序输入规模n的关系
T(n) = O(f(n))
关于上面的表达式，做如下介绍：
T(n): 程序执行时间关于数据输入规模n的函数
O(f(n)): 大O时间复杂度表示法
f(n)：程序执行代码行数总和关于输入规模n的函数
n: 数据输入规模
我们可以这么理解上面的表达式：
程序的执行时间T(n)和程序执行代码行数总和f(n)并不完全对等，因为我们的高级语言需要被解释编译才能被计算机执行，但是它们有一定的关系，理论上说，程序需要执行代码行数的总和f(n)越多，需要执行的时间T(n)就越长。所以，我们只需要关心执行代码行数的总和f(n)关于输入规模n的增长规模，为了更好地表达增长量级，我们使用大O来表示。
3.2 计算方法
我们来计算1 + 2 + 3 + .... n 的和
有如下两种算法
算法1:
private int method1(int n) {
int sum = 0; // 1次
for (int i = 1; i <= n; i++) { // n次
sum += i; // n次
}
return sum;
}
算法2:
private int method2(int n) {
return (n + 1) * n / 2; // 1次
}`
易知，两个算法代码执行行数总和f(n)如下：
算法1： f(n) = 2n + 1
算法2： f(n) = 1
图形表示如下所示：
image.png
可以看出，算法1中随着输入规模n的增长，f(n)呈线性增长; 而算法2，不管输入规模n为多少，f(n)恒为1。
那我们如何用大O来表示时间复杂度呢？
既然是表示增长规模，我们就要重点关注主要影响因素，忽略次要影响因素，总结如下：
- 找出程序执行代码行数总和f(n)关于输入规模n的函数，即f(n)
- 保留n的最高次项，去除其他次项，并把与最高次项相乘的常数设置为1
我们拿上面的两个算法来举例
首先，找到程序执行代码行数总和f(n)关于输入规模n的函数f(n)，即：
f(n) = 2n + 1 和 f(n) = 1
保留n的最高次项，去除其他次项，并把与最高次项相乘的常数设置为1：
n 和 1
所以两个算法的时间复杂度用大O表示为：
O(n) 和 O(1)
3.3 关于时间复杂度计算的探索
上面我们说到，计算时间复杂度的计算规则如下：
保留最高次项，并把与最高次项相乘的常数设置为1
根据这个规则，我们可以很轻易地算出下列算法的时间复杂度
| 序号 | 程序执行代码行数总和 | 时间复杂度 |
|---|---|---|
| 1 | f(n) = 1 | O(1) |
| 2 | f(n) = 3 | O(1) |
| 3 | f(n) = n + 1 | O(n) |
| 4 | f(n) = 2n + 1 | O(n) |
| 5 | f(n) = n^2 + 1 | O(n^2) |
| 6 | f(n) = n^2 + 2n + 1 | O(n^2) |
可以看到，虽然有6个算法，但是它们实际上只要3个时间复杂度来表示，分别为O(1)、O(n)、O(n^2)
我们把f(n)在图形上呈现出来：
image.png
从图形上可以看出
f(n) = n^2 + 2n + 1 和 f(n) = n^2 + 1 的增长规模是同一量级的，增长较快
f(n) = 2n + 1 和 f(n) = n + 1的增长规模是同一量级的，增长缓慢
f(n) = 3 和 f(n) = 1的增长规模是同一量级的，恒为常数，不增长
我们可以很容易地把6个算法分成3组，即它们对应的时间复杂度分别为：O(n^2)、O(n)、O(1)
3.4 如何在代码层面快速看出时间复杂度
1. 抓大放小
根据上面的规则，我们只要关注最高次项，在代码层面，只要关注最复杂的循环就可以了，比如下面的代码
private void test(int n) {
int sum = 0; // 1 次
for (int i = 0; i < n; i++) {
sum = sum + i; // n 次
}
// 这里是最复杂的循环
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; i++) {
sum = sum + i * j; // n^2 次
}
}
}
可以看出，f(n) = n^2 + n + 1，时间复杂度为O(n^2)。
在上面的代码里，我们只要找最复杂的循环，即双层循环，所以时间复杂度就是O(n^2)
2. O(n+m)
我们之前提到的数据输入规模，一般都是单个输入n，但程序可以存在多个输入，比如下面的算法，程序执行代码的行数，受到n和m两个参数的影响
private void oNAndM(int n, int m) {
int sum = 0; // 1 次
for (int i = 0; i < n; i++) {
sum = sum + i; // n 次
}
for (int i = 0; i < m; i++) {
sum = sum + i; // m 次
}
}
上面的f(n,m) = n + m + 1，因为不知道m和n的具体关系，所以m不能被忽略，这时候时间复杂度就是：O(n+m)
3. O(n * m)
上面提到的是n和m是平行的，没有相互影响，所以是相加，而如果n、m是嵌套的，则需要相乘，如下：
private void oNMultM(int n, int m) {
int sum = 0; // 1 次
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; i++) {
sum = sum + i * j; // n * m 次
}
}
}
可以知道f(n,m) = n * m + 1，则时间复杂度为：O(n * m)
其实2次方阶O(n^2)可以看成n和m相等的特殊情况
3.5 常见的时间复杂度
我们平常看到的算法时间复杂度一般都是以下这几种或这几种的组合
| 序号 | 时间复杂度 | 名称 |
|---|---|---|
| 1 | O(1) | 常数阶 |
| 2 | O(logn) | 对数阶 |
| 3 | O(n) | 线性阶 |
| 4 | O(n^k) | k次方阶 （比如k=2，即O(n^2)，则是平方阶） |
我们来看看这几种时间复杂度的算法体现
1. O(1)
f(n)不会随输入规模的n增大而变化
private void o1(int n) {
int i = n;
int sum = i * 2;
System.out.print("sum 为：" + sum);
}
可以看到，不管n为多少，f(n) 恒为3，就算f(n)恒为1000还是10000，时间复杂度都是O(1)
2. O(logn)
1. private int oLogn(int n) {
2. int i = 1;
3. while (i < n) {
4. i = i * 2;
5. }
6. return i;
7. }
可以看到，上述代码，主要的执行代码是循环体中的第4行代码，而上述的算法就是：i 初始化为1，每次循环乘以2，当 i > n时，结束循环，我们假设x次循环后，跳出循环，则i的值如下：
2^0、 2^1、 2^2.... 2^x ，所以满足2^x >= n，则x >= log2n（这里的2是底数）
所以x就是第一个大于等于log2n的整数，对数可以相互转换底数，且我们求的是数量级，所以我们可以不关心底数，直接用O(logn)来表示所有的对数阶
3. O(n)
private int oN(int n) {
int sum = 1;
for (int i = 0; i < n; i ++) {
sum = sum + i;
}
return sum;
}
这种线性阶，其实就是单个的for循环
4. O(n^2)
private void oN2(int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; i++) {
sum = sum + i * j; // n^2 次
}
}
}
这就是平方阶，其实就是2个循环。如果3个循环，就是立方阶，k个循环，就是k次方阶
4. 空间复杂度
空间复杂度表示的是存储空间跟数据输入规模的增长关系。
算法所需的存储空间可以使用如下表达式来表示：
S(n) = O(f(n))
跟时间复杂度类似，空间复杂度也是用大O来表示。
我们来分析如下两个算法的空间复杂度
算法1
public void o1() {
int i =1; // 1个
}
可以看到，我们只需要申请一个存储空间给i，所以空间复杂度为O(1)
算法2
public void oN(int n) {
int[] arr = new int[n]; // n个
}
易知，我们需要申请n个存储空间给数组arr，所以空间复杂度为O(n)
关于空间复杂度的计算跟时间复杂度一样，都是保留最高次项，并把与最高次项相乘的常数设置为1，这里就不详细描述了
5. 复杂度的排序
对于我们常见的复杂度，从低阶到高阶的排序如下：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2)
评估一个算法，时间复杂度和空间复杂度，都是越低越好
6. 应用
在后续的学习中，不管是各种数据结构的CURD操作还是评判各种算法好坏，我们都会从时间复杂度和空间复杂度两个方面来分析。
比如遍历HashMap的时间复杂度是多少？快速排序的平均时间复杂度和空间复杂度是多少？
我们没必要去记住它们，而是要懂得分析的方法，然后应用在日常的编程中，利于我们更好地选取数据结构和算法，你钢铁了，自然就战士了
7. 思考
关于《智行火车票》把加速包开到最大抢到票以后，智行上不付钱，然后登录12306在未完成订单中以原价购买
如果你是智行的员工
- 这种情况可以从技术层面避免吗？为什么？
- 如果不能避免，怎么去优化？
