时间复杂度是每个程序均有的属性，我们用渐进时间复杂度（Big $O$）来表示程序的运行效率。
部分程序的时间复杂度常常难以直接看出，因此我们需要借助一些工具来完成时间复杂度的计算。
下面介绍的递归结构分析法（主定理）可以在思考过程时计算想法程序的时间复杂度从而验证数据范围，而部分摊还分析常常在学习数据结构时使用到，从而加深理解以便进行拓展。
普通分析法
一般的顺序结构或循环结构的程序，我们可以直接得出其时间复杂度。
每个循环取最大运行范围，嵌套起来即为时间复杂度。
主定理
分析递归结构程序的时间复杂度。
本处仅仅给出主定理的结论，详细证明请参考这里。
主定理内容
大部分递归结构可以表示为这样的形式：$T(n)=aT(\frac nb)+f(n)$，其中$a\gt1,b\gt1$，可以证明对于$\frac nb$略去上下界不会对结果造成影响，则$T(n)$有这样的渐进界：
- 若$f(n)\lt n^{\log_ba}$，其中小于是多项式的小于，即$\exists\varepsilon\gt0,f(n)=O(n^{\log_ba-\varepsilon})$：
$T(n)=O(n^{\log_ba})\quad$（感性理解：太小$f(n)$代价不计） - 若$f(n)=O(n^{\log_ba})$：
$T(n)=O(f(n)\log n)$ - 若$f(n)\gt n^{\log_ba}$，其中大于是多项式的大于，即$\exists\varepsilon\gt0,f(n)=O(n^{\log_ba+\varepsilon})$：
$T(n)=O(f(n))\quad$（感性理解：太小递归无用）
举例
二分查找
满足条件$2$，故$T(n)=O(n^0\log n)=O(\log n)$
cdq分治
满足条件$2$，故$T(n)=O(n\log n)\log n=O(n\log^2 n)$
Karatsuba快速乘法
满足条件$1$，故$T(n)=O(\log_2^3n)$
摊还分析
分析操作间有关联性的程序均摊复杂度。
聚类分析
聚类分析中，我们将一连串的操作计算出其最坏时间复杂度$T(n)$，因此每个操作的均摊时间即为$\frac{T(n)}n$。
例.栈的维护
我们需要维护一个栈，它支持下列操作：
- $push(x)$：将$x$加入栈顶
- $pop()$：删除栈顶元素
- $multipop(k)$：删除栈顶$k$个元素
使用普通分析法，$multipop(k)$最坏花费$O(n)$的时间，因此$T(n)=\sum_{i=1}^nC_i\le n^2$，这显然是不科学的，因为不可能一直执行$multipop$，$multipop$是基于$push$操作的。
使用聚类分析法，发现$pop$的个数是小于等于$push$的个数的，因此：
因此，平均来看，$multipop(k)$花费$O(1)$的时间。
记账方法
记账法需要对每一个实际时间$C_{op}$的操作$op$设置一个均摊时间$\hat{C_{op}}$，使得对于$n$个操作的任意序列，满足$T(n)=\sum_{i=1}^nC_i\le\sum_{i=1}^n\hat{C_i}$。
对于每一个操作$op$：
- 若$\hat{C_{op}}\gt C_{op}$，则额外部分被储存起来作为预付的存款。
- 若$\hat{C_{op}}\lt C_{op}$，则使用存款支付差额。
对于所要求的$\sum_{i=1}^nC_i\le\sum_{i=1}^n\hat{C_i}$，实际上是要求存款不为负。
例.栈的维护
用记账法分析，设置$\hat{C_{op}}$如下：
| 操作$op$ | 实际时间$C_{op}$ | 均摊时间$\hat{C_{op}}$ |
|---|---|---|
| $push$ | $1$ | $2$ |
| $pop$ | $1$ | $0$ |
| $multipop$ | $\min\lbrace\mid S\mid,k\rbrace$ | $0$ |
不难发现，存款就是栈中元素个数，因此满足条件存款不为负。
势能分析
势能分析给每一个状态设置一个值，均摊时间就是基于这个值（势能函数）来计算的。
定义势能函数：$\varphi(S)$是状态$S$的势能函数。
定义均摊时间：$\hat{C_i}=C_i+\varphi(S_i)-\varphi(S_{i-1})$。
为保证$\sum_{i=1}^nC_i\le\sum_{i=1}^n\hat{C_i}$，需要保证$\varphi(S_n)\ge\varphi(S_0)$，即势能函数非负。
例.栈的维护
用势能分析分析，设置$\varphi(S)=$栈中元素个数$\left|S\right|$，则有：
| 操作$op$ | 实际时间$C_{op}$ | 势能差$\varphi(S_i)-\varphi(S_{i-1})$ | 均摊时间$\hat{C_{op}}$ |
|---|---|---|---|
| $push$ | $1$ | $1$ | $2$ |
| $pop$ | $1$ | $-1$ | $0$ |
| $multipop$ | $\min\lbrace\mid S\mid,k\rbrace$ | $-\min\lbrace\mid S\mid,k\rbrace$ | $0$ |
总结
聚类分析与后两种方法的不同点在于聚类分析将时间均摊到每一个操作上，因此每个操作的均摊时间均相同，而后两种方式则不同。
记账法与势能法有很多相同处，但记账法是自行设定均摊时间使其满足条件，势能法是设定非负权值计算得到均摊时间。
一般来说，若存在操作整体上的偏序关系，使用聚类分析较方便。记账法适用于均摊时间易猜得的时间复杂度进行猜测并验证，而势能法更考验配凑能力，将实际时间大的势能差设置为负，放在实际时间小的累积势能。
