数据结构
[TOC]
算法时间复杂度
在进行算法分析时，语句总的执行次数 $T(n)$ 是关于问题规模 n 的函数，进而分析 $T(n)$ 随 n 的变化情况并确定 $T(n)$ 的数量级。1
算法的时间复杂度，也就是算法的时间量度，记作 $T(n)=O(f(n))$ 。它表示随问题规模 n 的增大，算法执行时间的增长率和 $f(n)$ 的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中是 $f(n)$ 问题规模 n 的某个函数。
一般我们用大写O来体现时间复杂度的记法，我们称为大O记法。
综上，显然，随着 n 的增大， $T(n)$ 增长最慢的算法称为最优算法。此处指的是超过阈值后，并不是小规模的输入。
推导大O阶方法
推导大O阶：
- 用常数1取代运行时间中的所有加法常数。
- 在修改后的运行次数函数中，只保留最高项。
- 如果最高项存在且系数不是1，则去除与这个给项相乘的系数。
得到的结果就是大O阶。
常数阶
举个例子
1
2
3
int Sum = 0, n = 100;
Sum = (1 + n) * n / 2;
printf("%d",Sum);
这个算法的运行次数函数是 $f(n)=3$ 。根据上面第一条，显然为 $O(1)$ 。
再加强一下，我们将
1
Sum = (1 + n) * n / 2;
加到10句。实际上我们可以发现，无论 $n$为多少，代码的执行时间都不会随着 $n$ 的增长而增加的，执行时间恒定的算法，我们称之为具有 $O(1)$ 的时间复杂度，又叫常数阶。
注意：不管这个常数是多少，我们都记作 $O(1)$ ，而不是 $O(2)$ , $O(3)$ 之类，这是初学者常犯的错误。
线性阶
线性阶的循环结构会复杂很多。要确定某个算法的阶次，我们常常需要确定某个特定语句或某个语句集运行的次数。因此，我们要分析算法的时间复杂度，关键就是要分析循环结构的运行情况。
1
2
3
4
5
6
int i;
for( i =0; i < n ; i++)
{
//时间复杂度为O(1)的序列步骤
}
上述代码的循环时间复杂度为 $O(n)$，因为循环体中要执行n次。
对数阶
1
2
3
4
5
6
int Count = 1;
while( Count < n)
{
Count = Count * 2;
}
我们可以观察，当 Count < n时。在每次循环中，Count的取值序列为1,2,4,8,16...,，它是一个等比数列，增长直至大于等于n。
假设最后一次循环时，Count的值为m，即 $m \ge n$。我们可以得到以下关系：
我们可以通过求解 $2^{k} \ge n$ 来确定循环次数 $k$。解得 $k \ge \log _{2} n$ 。因此，循环的次数最多为 $O(log _{2} n)$ 。
$O(log _{2} n)$ 时间复杂度通常出现在问题规模 每次减半 或 递归调用 的情况下，例如二分法查找。
注：如无特殊声明，一般都是以2为底的对数。
平方阶
1
2
3
4
5
6
7
8
9
int i,j;
for( i = 0; i < n; i++)
{
for( j = 0 ; j < n ; j++)
{
//时间复杂度为O(1)的序列步骤
}
}
显然，外层每循环一次，内层就循环n次，所以时间复杂度为$O(n^{2})=O(n\times n)$ 。
相应的，如果外层循环改为m次，那么时间复杂度为$O(n\times n)$。因此我们可以总结得，循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。
我们再思考下面例子中时间复杂度为多少：
1
2
3
4
5
6
7
8
int i, j;
for ( i = 0; i < n; i++)
{
for ( j = i; j < n; j++)
{
//时间复杂度为O(1)的序列步骤
}
}
当 $i = 0$ 时，内循环执行了 n 次；当 $i=1$，时，内循环执行 $n-1$ 次，持续下去。因此我们有
\[n+(n-1)+(n-2)+...+1=\frac{n(n+1)}{2}=\frac{n^2}{2}+\frac{n}{2}=O(n^2)\]从这个例子不难得出，理解推导大O阶并不难，难得是对数列的一些相关运算，这更多的是考察你的数学知识和能力。
对于函数调用的时间复杂度分析也是如此，并不算太难。
常见的时间复杂度大小比较
常见的时间复杂度 从小到大 的顺序如下：（ $n$ 代表输入的大小， $c$ 代表一个固定的常数）2
| 时间复杂度 | 非正式术语 | 简介 |
|---|---|---|
| $O(1)$ | 常数复杂度 | 不管输入数据的大小如何，算法执行所需时间保持不变。 |
| $O(\log n)$ | 对数复杂度 | 通常出现在如二分搜索这样的算法中。 |
| $O((\log n)^c)$ | 对数的多项式复杂度 | 当c大于1时，表示多层嵌套的对数时间复杂度，它比单个对数复杂度增长得快。 |
| $O(n)$ | 线性复杂度 | 算法执行时间与输入数据的大小成正比。 |
| $O(n\log n)$ | 线性对数复杂度 | 许多高效的排序算法（如快速排序、归并排序）都有这个时间复杂度。 |
| $O(n^2)$ | 平方复杂度 | 执行时间是输入大小的平方。常见于简单的排序算法如冒泡排序，以及两层嵌套循环的算法。 |
| $O(n^c)$ | 多项式复杂度 | 这里的c是一个大于1的常数，表示多层嵌套循环的算法。 |
| $O(c^n)$ | 指数复杂度 | 随着输入大小的增加，执行时间呈指数增长。在很多情况下这是不切实际的，因为它的增长速率非常高。 |
| $O(n!)$ | 阶乘复杂度 | 最慢的一种，执行时间随着输入的大小呈阶乘方式增长。常见于解决旅行推销员问题等完全搜索算法。 |
最坏情况与平均情况
通常在编写算法时，如无特殊规定，我们提到的运行时间都是最坏情况。最坏情况时间复杂度是一种衡量算法性能的重要指标，它表示在最不利的情况下，算法的执行时间将达到的上限。
考虑最坏情况的原因是确保算法在任何输入情况下都能保持良好的性能。通过分析最坏情况，我们可以确定算法在最不利的情况下所需的时间和资源，并为设计和优化算法提供指导。
在实际应用中，最坏情况时间复杂度是一种保守的估计，它确保算法在任何输入下都能满足性能需求。然而，对于某些特定的应用场景，平均情况时间复杂度或者最好情况时间复杂度可能更具实际意义。
因此，平均运行时间是所有情况中最有意义的，因为它是期待的运行时间。