# 时间复杂度
在算法编程比赛中，你对一道题目编写的程序需要在题目指定的时间内通过测试数据来获取分数。
例如，一道题目的运行时间限制为 $1$ 秒，而如果你的程序需要运行超过 $1$ 秒的时间才能获得正确的输出，那么评测系统会给你返回提示 TLE（Time Limit Exceeded，超出运行时间）。
一个程序或算法执行所耗费的具体时间，从理论上是不能算出来的，必须上机运行测试才能知道，但我们不可能也没有必要对每个程序都上机测试，此时我们需要找到一个估算程序运行的效率和时间的标准。
## 语句执行次数与时间复杂度
我们可以通过统计每个程序中基本语句（原子操作）执行次数，就能预估哪个算法花费的时间多，哪个算法花费的时间少。简单来说，算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数记为 $T(n)$，其中变量 $n$ 表示的是输入数据的大小规模。
假设我们有两个程序 $A, B$ 在规模为 $n$ 的数据上运行，程序 $A$ 的用时 $T_A(n) = 100n$，程序 $B$ 的用时 $T_B(n) = n^2$。
- 现代计算机中一秒内大约能处理 $10^8$ 次基本语句操作。
- 当数据规模 $n$ 小于等于 $100$ 时，程序 $B$ 用时更短。
- 在 $1$ 秒的时间内，程序 $A$ 可以处理 $n = 10^6$ 规模的数据，而程序 $B$ 只能处理 $n = 10^4$ 规模的数据。
在衡量一个算法的执行效率时，我们不能只看它在某个数据规模下的用时，而需要看它的用时随着数据规模而增长的趋势，即时间复杂度。
## 大 $O$ 表示法
在算法竞赛中，我们经常使用渐进符号中的 **大 $O$ 符号** 来描述 $T(n)$ 增长趋势的上界，常用于描述**最坏时间复杂度**，也可以用来描述最好时间复杂度、平均（期望）时间复杂度。
- 最坏时间复杂度对应了算法在所有可能的输入规模中用时最长的那一个对应的时间复杂度。最好时间复杂度以此类推。
- 平均（期望）时间复杂度描述在所有可能的输入规模下的运行时间的平均值的时间复杂度（随机输入下期望用时的复杂度：所有可能的输入数据以均等概率出现的情况下，算法的期望运行时间）。
- 在不特别说明的前提下，讨论的时间复杂度均是最坏情况下的时间复杂度。
对于比较简单时间复杂度的计算，我们对 $T(n)$ 保留增长速度最高的项并去掉常系数就能得到时间复杂度（因为该项决定了算法执行时间的增长速度），并用大 $O$ 符号记录。例如，一个算法的 $T(n) = 3n^2 - 5n + 2$，那么它的时间复杂度记为 $O(n^2)$。
- $3n^2$ 是增长速度最高的项。
- $3, -5, 2$ 视为常系数。
算法的时间频度不同，但时间复杂度可能相同。例如，两个算法的时间频度分别为 $T(n)=n^2+3n+4$ 和 $T(n)=4n^2+2n+1$，它们的 $T(n)$ 不同，但时间复杂度相同，都为 $O(n^2)$。
## 计算时间复杂度
求解算法的时间复杂度的具体步骤是：
1. 找出算法中的基本语句；
2. 计算基本语句的执行次数 $T(n)$；
3. 对执行次数取增长速度最快的项并去掉常系数得到时间复杂度，并用大 $O$ 符号记录。
接下来我们将通过几个例子来分析常见的时间复杂度。
### 常数
```c++
int a = 1;
```
执行 $1$ 次变量定义和初始化语句，时间复杂度为 $O(1)$。
```c++
c = a;
a = b;
b = c;
cout << a << ' ' << b;
```
每条语句执行 $1$ 次，执行常数次语句，时间复杂度为 $O(1)$。
- 常数次输入输出语句的时间复杂度可以看作为 $O(1)$。
```c++
int Max(int a, int b){
if(a > b){
return a;
} else{
return b;
}
}
cout << Max(a, b);
```
每条语句最多执行 $1$ 次，执行常数次语句，时间复杂度为 $O(1)$。
```c++
for(int i = 1; i <= 10; i++){
cout << i << ' ';
}
```
循环控制与数据规模没有关系，执行常数次，时间复杂度为 $O(1)$。
### 线性
```cpp
for (int i = 1; i <= n; i++) {
}
```
循环语句执行 $T(n) = n$ 次，时间复杂度为 $O(n)$。
以下几种代码的时间复杂度也是 $O(n)$ 的，因为我们会忽略掉常系数和增长速度较低的项。
```cpp
for (int i = 1; i <= 5 * n + 17; i++) {
}
```
```cpp
for (int i = 1; i <= n + 114514; i++) {
}
```
```cpp
for (int i = 1; i <= n; i += 2) {
}
```
### 对数
```c++
for (int i = 1; i <= n; i *= 2) {
}
```
控制变量 `i` 从 $1$ 开始，每次循环增大一倍，直到超过 `n`。
循环会执行 $T(n) = [\log n] + 1$ 次，时间复杂度为 $O(\log n)$。
这里解释下 $\log$ 的含义：
- 从数学上讲，关于未知数 $x$ 的方程 $2^x = n$，它的解记为 $x = \log n$。
- 例如，$\log 32 = 5, \log 8 = 3, 4 \lt \log 24 \lt 5$。
### 根号
```c++
for (int i = 1; i * i <= n; i++) {
}
```
循环语句执行 $T(n) = [\sqrt{n}]$ 次，时间复杂度为 $O(\sqrt{n})$。
### 简单的循环嵌套
```c++
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cout << i << ' ' << j << '\n';
}
}
```
外重循环会执行 $n$ 次。
外重循环每次执行时，内重循环会执行 $i$ 次，内重循环总共执行 $1 + 2 + \dots + n = \frac{n \times (n + 1)}{2}$ 次。
语句执行次数为 $T(n) = n + \frac{n \times (n + 1)}{2} = \frac{1}{2}n^2 + n + \frac{1}{2}$，总时间复杂度为 $O(n^2)$。
```c++
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << i << ' ' << j << '\n';
}
}
```
有两个数据规模，外层循环执行 $n$ 次，内层循环一共执行 $n \times m$ 次，语句执行次数为 $T = n + nm$，总时间复杂度为 $O(nm)$。
```c++
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j += i) {
cout << i << ' ' << j << '\n';
}
}
```
外重循环会执行 $n$ 次。
外重循环每次执行时，内重循环会依次执行 $n, [\frac{n}{2}], [\frac{n}{3}], \dots, [\frac{n}{n}]$ 次。
原子操作总共执行 $T(n) = n + [\frac{n}{2}] + [\frac{n}{3}] + \dots + [\frac{n}{n}]$ 次。在信息学竞赛中，该程序的时间复杂度被称作为调和级数复杂度，数学上可以证明时间复杂度为 $O(n \log n)$。
```c++
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
for (int k = 1; k <= j; k++) {
cout << i << ' ' << j << ' ' << k << '\n';
}
}
}
```
第一重循环执行 $n$ 次，第一重循环每次执行时，第二重循环执行 $i$ 次，第二重循环每次执行时，第三重循环执行 $j$ 次。数学上可以证明，总时间复杂度为 $O(n^3)$。
### 并列
如果算法程序由多个程序片段组成，那么总时间复杂度取其中时间复杂度最高的片段。
```cpp
for (int i = 1; i <= n; i++) {
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
}
}
for (int i = 1; i <= n; i++) {
}
```
上述程序的时间复杂度为 $O(n^2)$。
```cpp
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
}
}
for (int i = 1; i <= m; i++) {
}
```
上述程序的时间复杂度为 $O(n^2 + m)$，因为 $n^2$ 和 $m$ 都不能被认为是增长速度较低的项。
### 递归
请查看其他章节。
## 常见的时间复杂度
按数量级递增的方式，我们可以列出信息学竞赛中最常见的几种时间复杂度。
| 名称 | 记号 | 常见场景 |
| :------: | :---------------------: | :-----------------------------: |
| 常数 | $O(1)$ | 解方程，使用数学公式计算答案 |
| 对数 | $O(\log n)$ | 二分，set、map 或优先队列的操作 |
| 根号 | $O(\sqrt{n})$ | 判断质数，质因数分解 |
| 线性 | $O(n)$ | 读入长度为 $n$ 的数组 |
| 线性对数 | $O(n \log n)$ | `sort` 排序 |
| 平方 | $O(n^2)$ | 选择排序、插入排序、冒泡排序 |
| 多项式 | $O(n^3), O(n^4), \dots$ | 枚举 $k$ 元组 |
| 指数 | $O(2^n), O(3^n), \dots$ | 枚举子集、子集的子集 |
| 阶乘 | $O(n!)$ | 枚举全排列 |
下图描述了几种常见的时间复杂度的增长速度。
### 估算程序执行时间
目前常用评测机的算量大约在一秒执行 $10^8$ 条循环语句,可以将数据规模的实际值带入时间复杂度进行计算，从而估算程序执行时间。
下表展示了一些常见时间复杂度在 $1$ 秒内能执行的数据规模。
| 量级 | 数据规模 |
| :----------: | :--------: |
| $O(\log n)$ | $2^{10^8}$ |
| $O(\sqrt n)$ | $10^{16}$ |
| $O(n)$ | $10^8$ |
| $O(n^2)$ | $10^4$ |
| $O(2^n)$ | $25$ |
| $O(n!)$ | $11$ |
**我们也可以根据题目中的数据范围来推测算法的时间复杂度。**
| $n \le $ | 可能的时间复杂度 |
| :-------: | :---------------: |
| $10$ | $n!$ |
| $20$ | $O(n \times 2^n)$ |
| $25$ | $O(2^n)$ |
| $100$ | $O(n^4)$ |
| $500$ | $O(n^3)$ |
| $8000$ | $O(n^2)$ |
| $10^5$ | $O(n \sqrt n)$ |
| $10^6$ | $O(n \log n)$ |
| $10^7$ | $O(n)$ |
| $10^{12}$ | $O(\sqrt n)$ |
| $10^{18}$ | $O(\log n), O(1)$ |
## 常数优化
常数（包括常数项和常系数）指代一些时间复杂度相同但运行时间有些许不同的操作。例如在有序数组上进行二分查找和在 map/set 中进行查找的时间复杂度都是 $O(\log n)$，但是前者的运行速度会更快。
在大 $O$ 表示法中，常数是被忽略掉的部分。在小部分运行时间非常紧张的题目中，如果你的常数较大，你的程序可能依然会得到 TLE 的结果。此时我们需要对程序做一些常数优化。常见的优化方法有：
- 使用较快的输入输出方法，例如关闭流同步、使用换行符 `\n` 替代 `endl` 等。
- 减少不必要的循环次数。
- cache 优化。
现在不清楚常数优化没关系，在以后的学习中会经常遇见。
## 一些练习
```c++
// 猜测以下程序片段的复杂度
void fun(){
if(flag){
for(int i=0;i<n;i++){
for(int j=0;j<n;i++){
cout << 1;
}
}
}
else{
for(int i=0;i<n;i++){
cout << 2;
}
}
}
// O(n ^ 2)
void fun(int n){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int k=1;
while(k<=n){
k = 5*k;
j = k;
}
}
}
}
// O(nlogn)
int fact(int n){
if (n<=l) return 1;
return n*fact(n-1);
}
//O(n)
void fun(int n){
int x=2;
while(x<n/2)
x=2*x;
}
//O(logn)
void fun (int n){
int i=0;
while(i*i*i<=n) i++;
}
//O( $\sqrt[3]n$ )
void fun(int n,int l){
for(i=n-l;i>l;i--)
for(j=1;j<i;j++)
if(A[j]>A[j+l]) swap(a[i],a[j]);
}
// O(n^2)
void fun(int n){
int cnt = 0;
for(i=l;i<=n;i++)
for(j=1;j<=i;j*=2)
cnt++;
}
//O(nlogn)
int fun(int n){
if( n == 1 ) return 1;
else return 2 * fun(n/2) + n;
}
//O(logn)
void fun(int n,int l){
i=l;k=0;
while(i<n-l){
k=k+10*i;
i++;
}
}
//O(n)
void fun(int n){
y=0;
while((y+1)*(y+1)<=n)
y=y+1;
}
//O(sqrt(n))
void fun(int n){
/// a[N] 是一个从小到大的数组 找第一个大于等于x的数
int l = 1, r = n;
while(l <= r){
int mid = (l + r) >> 1;
if( a[mid] < x ) l = mid + 1;
else r = mid - 1;
}
}
void fun(){
string s[N];
for(int i = 0; i < n - 1; ++i){
if( s[i] > s[i + 1] ) swap(s[i], s[i + 1]);
}
}
/// O(n^2)
```