## 算法的时间复杂度和空间复杂度
> 程序 = 算法 + 数据结构
【目录】
---
[TOC]
---
### 时间复杂度
> 指的是算法的时间耗费。
在算法的每个步骤中，可能有若干条语句，而频度就是指每条语句的执行次数。
简单来说，以一条基本语句的执行时间为基本单位，该算法所有语句中总的基本语句的执行次数就是该算法的时间耗费，它是该算法所求解的问题规模 ` n ` 的函数。当问题的规模`n`趋向无穷大时，我们就把时间复杂度的数量阶称为算法的渐进时间复杂度。一般我们把渐进时间复杂度称为算法的时间复杂度，记作“O”(Order)，它有严格的数学意义：若`T(n)`和`f(n)`是定义在正整数集合的两个函数，则`T(n)=O(f(n))`表示存在正常的常数`C`和`n0`，使得当` n ≥ n0 `时都满足` 0 ≤ T(n) ≤ C * f(n)`。
各个时间复杂度大小关系：
$$
O(1) < O(\log_2n) < O(n) < O(n\log_2 n) < O(n^2) < O(n^3) < O(2^n) < O(n^n) < O(n!)
$$
> 常数阶 O(1)
算法中语句执行次数为常数，则时间复杂度为`O(1)`
```java
int i = 1;// 频度1
i++;// 频度1
// 频度总和是一个常数
```
> 对数阶 O(log_2n)
```java
public int calc(int number) {
int return_number = 1;// 频度1
while(return_number <= number) {
return_number = return_number * 2;// 假设频度是 f(n) , 2^f(n) ≤ n; f(n) ≤ log2n
}
return return_number;
}
// 总和： log2n + 1 ，所以 T(n) = O(log2n)
```
> 线性阶 O(n)
```java
public int calc(int number) {
int a = 0;// 频度1
while(number > 0) {
a += numer;// 频度 n
number--;// 频度 n
}
return a;
}
// 频度总和：2n + 1，所以 T(n) = O(n)
```
> 线性对数阶O(nlog_2 n)
>
> 结合 n 和 log2n
> 平方阶O(n^2)
>
> eg：2个for循环
> 立方阶O(n^3)
>
> eg：3个for循环
> k次方阶O(n^k)
>
> eg：n个循环
> 指数阶O(n^n)
>
> eg：n维数组
#### 【常见排序算法时间复杂度】
| 算法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 | 备注 |
| :---: | :------: | :----------: | :----: | :------: | :-----------------------------------: |
| 冒泡 | O(n^2) | O(n^2) | 稳定 | O(1) | n较小时，较好 |
| 交换 | O(n^2) | O(n^2) | 不稳定 | O(1) | n较小时，较好 |
| 选择 | O(n^2) | O(n^2) | 不稳定 | O(1) | n较小时，较好 |
| 插入 | O(n^2) | O(n^2) | 稳定 | O(1) | 大部分已排序时较好 |
| 基数 | O(logRB) | O(logRB) | 稳定 | O(n) | B是真数0-9<br />R是基数（个，十，百） |
| Shell | O(nlogn) | O(n^s) 1<s<2 | 不稳定 | O(1) | s是所选分组 |
| 快速 | O(nlogn) | O(n^2) | 不稳定 | O(nlogn) | n大时较好 |
| 归并 | O(nlogn) | O(nlogn) | 稳定 | O(1) | n大时较好 |
| 堆 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n大时较好 |
#### 【经验规则】
- 其中c是一个常量，如果一个算法的复杂度为c 、 log\*2n 、n 、 nlog2n,那么这个算法时间效率比较高
- 如果是2^n ,3^n ,n!，那么稍微大一些的n就会令这个算法不能动了，居于中间的几个则差强人意。
#### 【求算时间复杂度具体步骤】
- 找出算法中的基本语句
- 通常是内层循环的循环体
- 计算基本语句的执行次数的数量级
- 保证基本语句执行次数的最高次幂正确，可以忽略低次幂和最高次幂的系数，集中注意力到最重要的一点上：增长率。
- 用大O记号表示算法的时间性能
#### 【分析法则】
- 一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间
- <span style="color:red">顺序结构</span>,需要依次执行一系列语句所用的时间可采用大O下"求和法则"
**求和法则**:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))
特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))
- <span style="color:red">选择结构</span>,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间
- <span style="color:red">循环结构</span>,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"
**乘法法则**: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1*T2=O(f(n)*g(n))
- 对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度
另外还有以下2个运算法则:(1) 若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一个正常数
#### 【例子】
1、
```java
for (int i=0; i<n; i++){// 执行 n+1 次
for (int j=0; j<n; j++) {// n*(n+1)
x = x + 1; // n*n
}
}
```
总的次数：n+1 + n*(n+1) + n * n = 2n^2 + 2n + 1，当 n 趋向于无穷大的时候，其执行的次数和 n^2 是同一个数量阶，所以时间复杂度是 O(n^2)
2、
```php
for (int $i=0; i<1000; $i++){// 执行 1001 次
for (int $j=0; $j<1000; $j++) {// 1000*1001
$x = $x + 1; // 1000 * 10000
}
}
```
总的次数是一个常数，与常数同阶，时间复杂度是O(1)
3、在一个有序的数组中查找关键字K。
- 二分查找（折半查找）
无论是K 处于前半部分，还是后半部分，都是忽略另外一部分，直到找到关键字K（或者没有在数组中），这个过程至多重复 log2n 次
```java
static int binarySearch(int K, int[] array, int left, int right)
{
int l = left - 1;
int r = right + 1;
while(l+1 != r) {
int i = (l+r)/2;
if (K < array[i]) {
r = i;
}
if (K == array[i]) {
return i;
}
if (K > array[i]) {
l = i;
}
}
return -1;
}
```
【参考链接】
[算法的时间复杂度和空间复杂度-总结](https://blog.csdn.net/zolalad/article/details/11848739)
### 空间复杂度
> 该算法所耗费的空间，也是问题规模 n 的函数。一般是指渐进空间复杂度。记作：S(n) = O(f(n))
例子：
1、一个包含了 n 个整数的一维数组空间代价是多少？
- 如果每个整数占有 c 个字节空间，则整个数组占用 cn 个字节空间，其空间复杂度就是 O(n)。
- 在存储结构中，例如指针实际上是附加信息的开销，称为结构性开销。理论上来说，结构性开销应该尽量小，而访问路径又应该尽可能的多且有效。
2、信息压缩和解压缩
### 【总结】
- 算法分析时，除非特别声明，都是按照最坏情况分析。我们通常所说的算法的复杂度一般是时间复杂度和空间复杂度的合称。
- 解决问题的步骤应该是： 先调整算法，后调整代码。
