# 问题规模-时间复杂度速查
### 「问题规模-时间复杂度-操作次数」对照表
| 输入规模 n | $O(\log n)$ | $O(n)$ | $O(n\log n)$ | $O(n^2)$ | $O(n^3)$ | $O(2^n)$ | $O(n!)$ |
| :--------- | :---------- | :----- | :----------- | :-------- | :-------- | :------------- | :-------------- |
| 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 |
| 2 | 1.00 | 2 | 2.00 | 4 | 8 | 4 | 2 |
| 3 | 1.58 | 3 | 4.75 | 9 | 27 | 8 | 6 |
| 4 | 2.00 | 4 | 8.00 | 16 | 64 | 16 | 24 |
| 5 | 2.32 | 5 | 11.61 | 25 | 125 | 32 | 120 |
| 6 | 2.58 | 6 | 15.51 | 36 | 216 | 64 | 720 |
| 7 | 2.81 | 7 | 19.65 | 49 | 343 | 128 | 5040 |
| 8 | 3.00 | 8 | 24.00 | 64 | 512 | 256 | 40320 |
| 9 | 3.17 | 9 | 28.53 | 81 | 729 | 512 | 362880 |
| 10 | 3.32 | 10 | 33.22 | 100 | 1000 | 1024 | 3628800 |
| 100 | 6.64 | 100 | 664.39 | $10^4$ | $10^{6}$ |
gt;10^{30}$ ✖ | gt;10^{157}$ ✖ |
| $10^3$ | 9.97 | $10^3$ | 9965.78 | $10^{6}$ | $10^{9}$ | gt;10^{301}$ ✖ | gt;10^{2567}$ ✖ |
| $10^4$ | 13.29 | $10^4$ | $1.3*10^5$ | $10^{8}$ | $10^{12}$ | ✖ | ✖ |
| $10^5$ | 16.61 | $10^5$ | $1.7*10^6$ | $10^{10}$ | $10^{15}$ | ✖ | ✖ |
| $10^6$ | 19.93 | $10^6$ | $2*10^7$ | | | | |
| $10^7$ | 23.25 | $10^7$ | $2*10^8$ | | | | |
| $10^9$ | 29.90 | | $3*10^{10}$ | | | | |
| $10^{15}$ | 49.83 | | | | | | |
"✖"表示已超出计算范围。
时间复杂度排序： $O(\log n) < O\sqrt{n} < O(n)$ < $O(n\log n)$ < $O(n^2)$ < $O(n^3)$ < $O(2^n)$ < $O(n!)$
### 由 "输入规模" 推测可用算法的时间复杂度上限
以 C++为例，**各个 OJ 平台上 1s 时限下的操作数大约在 $10^7\sim 10^8$ 次操作**。
通常：
- 问题规模**在 $10^2$** **时**，**最次可用 $O(n^3)$ 的解法**；
- 问题规模**在 $10^3$ 时，最次可用 $O(n^2)$ 的解法**；
- 问题规模**在 $10^4\sim~10^5$ 时，最次可用 $O(n\log n)$ 的解法**；
- 问题规模**在 $10^6\sim 10^7$ 时**，**最次可用 $O(n)$ 的解法**；
- 问题规模大于 $10^7$ 时，**只能是 $O(\log n)$ 或者 $O(\sqrt{ n })$ 的解法**。
> [!NOTE]
> 
%%
> 
> 参考：
>
> [由数据范围反推算法复杂度以及算法内容](https://www.acwing.com/blog/content/32/)
%%
<br><br>
# 复杂度定义
- 时间复杂度：$T(n)$ = 用算法**求解某一输入规模为 n 的问题，所需执行的基本操作次数**。
- 空间复杂度：$S(n)$ = 用算法**求解某一输入规模为 n 的问题，所需占用的存储单元数**。
# 复杂度表示法
三种复杂度表示法如下：
- **大 $O$ 表示法**：确定复杂度的**上界**。
- **大 $\Omega$ 表示法**：确定复杂度的**下界**。
- **大 $\Theta$ 表示法**：确定复杂度的**上下确界**，一个准确的确界。
### 大 $O$ 表示法
**大 $O$ 表示法**又称**渐进表示法**，采用**大 $O$ 记号**（big-O notation），用于描述算法的时间复杂度或空间复杂度。
**大 $O$ 表示法**的含义： **若存在常数 $c>0$ ，当 $n >> 2$ 时，有 $T(n)<c\cdot f(n)$，则称 $T(n)=O(f(n))$** ，表示**时间复杂度 $T(n)$ 渐进于上界 $f(n)$**。
应用**大 $O$ 表示法**时应注意：（1）**忽略常数项、低阶项**；（2）**常底数无所谓，统一以 $\log$ 表示**。
<br><br>
# 复杂度分析
复杂度分析的主要方法：
- 针对「**迭代**」的时间复杂度分析方法：**级数求和**
- 针对「**递归**」的时间复杂度分析方法：（1） **递归跟踪** 、（2）**递归树分析** 、（3）**递推方程求解** 、（4）**主方法**
<br><br>
# 「迭代」的时间复杂度分析
### 常见**级数求和**与对应的**时间复杂度**
| 级数 | 公式 | 时间复杂度 |
| --------------- | ---------------------------------------------------------------------- | -------------------- |
| **算术级数** | $T(n)=1+2+3+\dots+n=\large\frac{n(n+1)}{2}$ | $O(n^2)$ |
| | | |
| **几何级数** | $T(n)=a^0+a^1+a^2+\cdots+a^n=\large\frac{a^{(n+1)}-1}{a-1}$ | $O(a^n)$; $a > 1$ |
| （与级数的**末尾项**同阶） | 示例 1：$1+2+4+8+\cdots+2^n=2^{n+1}-1$ | $O(2^n)$； $a==2$ |
| | 示例 2：$1+2+4+8+\cdots+2^{\log n}=2^{(\log n+1)}-1$ | $O(n)$； $a==2$ |
| | | |
| **调和级数** | $T(n)=1+\large\frac{1}{2}+\frac{1}{3}+\cdots\frac{1}{n}=\approx\ln(n)$ | $O(\log n)$ |
| | | |
| **幂方级数** | 平方级数：$T(n)=1^2+2^2+3^2+\dots+n^2=\large\frac{n(n+1)(2n+1)}{6}$ | $O(n^3)$ |
| （比幂次高出一阶） | 立方级数：$T(n)=1^3+2^3+3^3+\dots+n^3=\large\frac{n^2(n+1)^2}{4}$ | $O(n^4)$ |
| | | |
| **对数级数** | $T(n)=\log1+\log2+\log3+\cdots+\log n=\log(n!)$ | $O(n\log n)$ |
### 迭代（嵌套循环）的时间复杂度分析
情况一：外层循环次数为 $n$，内层循环次数同为 $n$ 或 $i$，渐进复杂度都是 $O(n^2)$，如下图。
情况二：外层循环令 **$i$ 值从 $1$ 起每次乘以 2 翻倍直至为 $n$**，**内层循环次数即为 $i$ 值**。
两层循环的 **总操作次数** 呈现**几何级数** $1+2+4+\cdots+n$，**尾项是 $n$**，因此渐进时间复杂度是 $O(n)$。
（如下图的左上角，最后一次尾项目的操作次数为 n）。
情况三：外层 n 次迭代，内层的 $j$ 值**每次翻倍**，因此在外层的每轮迭代中内层的**总操作次数相当于对 $i$ 取对数**，总的时间复杂度为 $n\log n$，如下图。
<br><br>
# 「递归」的时间复杂度分析
四种方法：（1） **递归跟踪** 、（2）**递归树分析** 、（3）**递推方程求解** 、（4）**主方法**
## 方法一：递归跟踪（recursion trace）
> 适用于"**线性递归**"，例如常见于 **"减而治之"的情况**，链表反转、数组反转。
**检查每个==递归实例==**，累计**各个递归实例下==所需操作次数的总和==** 即为算法的时间复杂度。
<br>
## 方法二：分析**递归树**
> 适用于 **树形递归**，例如常见于 "**分治**" 的情况。
分析 **递归树的==深度==** 和 **==每一层的节点数==（即每一层递归调用展开的次数）**，其中，**每个节点对应==一次递归调用==产生的代价**。
以**分治形式的递归**为例，每次**递归调用两个函数**再合并，意味着**每一层的递归调用数量大约是上一层的两倍**，是指数级别的增长。
##### 示例：以求解斐波拉契数列第 n 项为例
```c++
int fibonacci(int n) {
if (n < 2) return n;
return fibonacci(n-1) + fibonacci(n-2); // 每一层的递归调用数量是上一层的两倍
}
```
- 分析**递归树==每层的节点数==**：
- 初始调用 `fibonacci(n)`。这个调用**分裂为两个子调用**：`fibonacci(n-1)` 和 `fibonacci(n-2)`。
- 这种分裂在每个递归步骤中都会发生，直到到达基本情况（`n < 2`）。
- 每个递归调用（树中一个节点）本身的处理时间是常量，因此整体时间复杂度取决于**递归树中的节点总数**。
- 分析**递归树的==深度==**：
- 树的深度为 $n$ 。`finbonaci(n-1)` 侧从 n 开始每次减少 1，一直减少到`n < 2`，约需要 n 次，**故深度为 n**。
由上，每一层的递归调用数量是上一层两倍，即**树的节点数每次乘以二**，递归树的深度约为 $n$，**各层递归调用的总次数**构成一个**几何数列**：$1+2+4+\cdots+2^n$，所以总的**时间复杂度为 $O(2^n)$**。
如下图所示：
<br>
## 方法二：根据时间复杂度 $T(n)$ 的**递推方程**推导出 $T(n)$ 的**直接表达式**
##### 示例：Quick-Select 快速选择算法的时间复杂度分析
该算法的时间复杂度递归式可写为：$T(n)=T(\frac{n}{2})+O(n)$，单侧做排序的时间复杂度开销记为 $O(n)$。
$
\begin{aligned}
T(n) &=T\left(\frac{n}{2}\right)+n \\
T\left(\frac{n}{2}\right) &=T\left(\frac{n}{4}\right)+\frac{n}{2} \\
T\left(\frac{n}{4}\right) &=T\left(\frac{n}{8}\right)+\frac{n}{4} \\
&\vdots \\
T(1) &=T(0)+1
\end{aligned}
$
将上面各项等式左右两侧累加并抵消，得到 $T(n)=T(0)+1+2+4+\cdots+\frac{n}{4}+\frac{n}{2}+n$，后面一堆是 "**几何级数**"，尾项为 $n$，因此总时间复杂度为 $O(n)$。
<br><br>
## 方法四：主方法（Master Theorem）
主方法：一种**快速求解递归关系式**的方法。通过主方法可以**直接得出**许多**分治算法**的时间复杂度。
#### 时间复杂度 $T(n)$ 的递归关系式表示
时间复杂度 $T(n)$ 的 **==递归==关系式**可表示为如下形式：
其中，$a\ge1,b\gt1$。
上式描述了一个**分治算法**：拆成 **$a$ 个子问题**，每个子问题的规模是原问题的 $\large \frac{1}{b}$，**分解与合并**步骤的**时间开销为 $f(n)$。**
### 主定理
主方法依赖于以下定理：**==主定理==**
主定理是**将 $f(n)$ 与 $n^{\large \log _ba}$ 进行比较**，根据二者的关系**划分成三种情况**，分别**对应不同的时间复杂度**。
**直觉上**来说，二者中的**较大者**决定了递归式的解。
- 情况一
- 若 $f(n)$ 在**多项式意义**上**小于** $n^{\large \log _ba}$ （**必须渐进小于**，相差一个因子 $n^\epsilon, \epsilon>0$），<br>即 $f(n)=n^{\log_ba-\epsilon}$ ，则有 $T(n)=\Theta(n^{\large \log _ba})$。
- 情况二
- 若 $f(n)=n^{\large \log _ba}$，则结果乘上一个对数因子 $\log n$，有 $T(n)=\Theta(n^{\large \log _ba}\log n)$。
- 情况三
- 若 $f(n)$ 在**多项式意义**上**大于** $n^{\large \log _ba}$ （**必须渐进小于**，相差一个因子 $n^\epsilon, \epsilon>0$），<br>即 $f(n)=n^{\log_ba+\epsilon }$，<br>且同时满足"**正则条件**" ： $af(\frac{n}{b}))\le cf(n)$ 对某个常数 $c<1$ 和所有足够大的 $n$ 成立，<br>则 $T(n)=\Theta(f(n))$。
> [!NOTE]
> 正则条件即 **多个子问题**的**分解合并的总开销** $af(\frac{n}{b})$ 严格小于原问题的开销 $f(n)$。
> 在 $c<1$ 时，显然有 $af(\frac{n}{b})\le cf(n)<f(n)$。
总结：
| | 条件 | 时间复杂度 |
| --- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ---------------------------------------- |
| 情况一 | 若 $f(n)$ 在**多项式意义**上**小于** $n^{\large \log _ba}$ （**必须渐进小于**，相差一个因子 $n^\epsilon, \epsilon>0$），即 $f(n)=n^{\log_ba-\epsilon}$ | $T(n)=\Theta(n^{\large \log _ba})$ |
| 情况二 | 若 $f(n)=n^{\large \log _ba}$，则结果乘上一个对数因子 $\log n$ | $T(n)=\Theta(n^{\large \log _ba}\log n)$ |
| 情况三 | 若 $f(n)$ 在**多项式意义**上**大于** $n^{\large \log _ba}$ （**必须渐进小于**，相差一个因子 $n^\epsilon, \epsilon>0$），即 $f(n)=n^{\log_ba+\epsilon }$，<br>且同时满足"**正则条件**" ：$af(\frac{n}{b}))\le cf(n)$ 对某个常数 $c<1$ 和所有足够大的 $n$ 成立。 | $T(n)=\Theta(f(n))$ |
> [!caution]
>
> 并非所有的递归式都可以应用主方法，**必须是上述三种情况之一**。
> 除上述三种情况外， $f(n)$ 还可能为如下情况，此时不能应用主方法。
>
> - 情况 1 和 2 之间存在空隙，$f(n)$ 可能小于 $n^{\large \log _ba}$ 但**不是多项式意义上的小于**。
> - 情况 2 和 3 之间存在间隙，$f(n)$ 可能大于 $n^{\large \log _ba}$ 但**不是多项式意义上的大于**，或者**正则条件不成立**。
<br><br>
### 主方法应用示例
#### 情况一示例
> 示例：
> 
> [!example] **==遍历平衡二叉树==**的时间复杂度
>
> 递推式可写为：$T(n)=2T(\frac{n}{2})+O(1)$
>
> 根据主方法，$a=b=2$，有 $n^{\log_ba}=n^{\log_22}=n$，
>
> 而 $f(n)=O(1)$，所以 $f(n)<n^{\log_ba}$ 。存在 $\epsilon=1$，使得 $f(n)=n^{\log_ba-\epsilon}=n^0=O(1)$ 成立，
>
> **满足多项式意义上的小于**，对应主方法中的第一种情况，所以 $T(n)=O(n^{\log_ba})=O(n)$。
#### 情况二示例
> 示例：
> 
> [!example] **==归并排序==**的时间复杂度分析
>
> 递推式可写为： $T(n)=2T(\frac{n}{2})+O(n)$，合并两个有序数组的时间开销为 $O(n)$。
>
> 根据主方法，$a=b=2$，有 $n^{\log_ba}=n^{\log_22}=n$，
>
> 而 $f(n)=O(n)$，因此有 $f(n)=\Theta(n^{\log_b a})$
>
> 对应主方法中的**第二种情况**，所以 $T(n)=O(n^{\log_ba}\log n)=O(n\log n)$
> [!example] **==二分查找==**的时间复杂度分析
>
> 递推式可写为：$T(n)=T(\frac{n}{2})+O(1)$
>
> 根据主方法，$a=1,b=2$，有 $n^{\log_ba}=n^{\log_21}=n^0=1$，
>
> 而 $f(n)=O(1)$，因此有 $f(n)=\Theta(n^{\log_b a})$
>
> 对应主方法中的**第二种情况**，所以 $T(n)=O(n^{\log_ba}\log n)=O(\log n)$
>
#### 情况三示例
> 示例：
>
> 
>
> 说明：
> 显然 $f(n)=n\log n > n^{\log_b a}=n^{\log_4 3}$，因此**直接尝试套用情况三**，有 $f(n)=\Omega(n^{\log_ba+ \epsilon})$，无需求出 $\epsilon$ 具体值，继续看正则条件是否成立。当 $n$ 足够大时，要使得下式成立：
> $
> \begin{align}
> af(\frac{n}{b})\le cf(n)\;\;
> \\
> 3f(\frac{n}{4})=3\cdot\frac{n}{4}\log \frac{n}{4}\le cf(n)=c\cdot n\log n
> \\
> \frac{3}{4}\log \frac{n}{4}\le c\cdot \log n
> \\
> \frac{3}{4}\log \frac{n}{4}<\frac{3}{4}\log n\le c\log n
> \end{align}
> $
> 当 $c\ge\frac{3}{4}$ 时上式成立，因此可取 $c=\frac{3}{4}$。所以情况三满足，$T(n)=\Theta(n\log n)$
> [!example] **==QuickSelect 算法==（找出数组中第 k 大的元素**）的时间复杂度分析
>
> 递归式可写为：$T(n)=T(\frac{n}{2})+O(n)$，单侧做排序的时间复杂度开销记为 $O(n)$。
>
> 根据主方法，$a=1,b=2$，有 $n^{\log_b{a}}=n^{\log_21}=1$，
>
> 而 $f(n)=O(n)$，有 $f(n)=n^{\log_ba+\epsilon}$ 取 $\epsilon=1$ 成立，
>
> 同时满足 $aT(\frac{n}{b})=T(\frac{n}{2})\le cf(n), c\le1$ 成立。
>
> 对应主方法中第三种情况，所以 $T(n)=O(f(n))=O(n)$。
#### 主方法不适用的情况
无法应用**主方法求解**的示例：
说明：
虽然有 $f(n)=n\log n>n^{\log_b a}=n^{\log_22}=n$ ，但**并不是多项式意义上的大于**，
因为不存在一个 $\epsilon>1$ 使得 $f(n)=n^{\log_ba+\epsilon}$ 即 $ n\log n=n^{1+\epsilon}$ 即 $\log n=n^\epsilon$ 对所有足够大的 $n$ 成立。
所以无法应用主定理求解。
<br><br>
%%
# 回溯法时间复杂度分析
以回溯法进行字符串分割为例
长度为 $L$ 的字符串，共 $L-1$ 个可分割的位置，因此可能的回溯结果是 $2^{L-1}$ 种。
值为 $x$ 的数，其十进制位的位数为 $d=\lfloor 1+\log_{10}{x}\rfloor$。
%%
# "平均"复杂度分析与 "均摊"复杂度分析
均摊复杂度分析示例：
例如 C++中 vector 容器的动态扩容，采用 "倍增"策略。