快速搞定常用时间复杂度分析
扫描二维码
随时随地手机看文章
在数据结构与算法的学习过程中，如果只学会了其特点，用法，而并没有掌握算法复杂度的分析，那就相当于只学会了皮毛，而没有掌握其灵魂。
由于算法复杂度的分析较为重要，该部分会分为两篇文章：今天会介绍怎么分析算法复杂度，以及常见的复杂度分析。
首先会教大家怎么去分析算法复杂度，算法复杂度主要有两类：
-
时间复杂度
-
空间复杂度
算符复杂度的表示一般采用大O复杂度表示法。
时间复杂度分析
时间复杂度的全称是监禁时间复杂度，表示算法的执行时间与数据规模之间的增长关系。
首先，看下面这函数，假设每行代码的运行时间为t，那么这段代码总的运行时间为多少呢？
int Test(int n) { int i = 1; int k = 1; int j = 0; for(i = 0; i <= n; ++i) { k = 1; for(; k <= n; ++k) { j = j + i * k; } } }
-
第2、3、4行代码的运行时间分别为1t
-
第5、6行代码的运行时间分别为n * t
-
第7、8行代码的运行时间分别为n * n
-
这段代码总的运行时间为
由上述代码可知，一段代码的运行时间T(n)与每行代码的执行次数n成正比，则T(n) = O(f(n))。
将上述代码的运行时间代入公式得：
这便是大O时间复杂度表示法。
该表示法并非表示代码的运行时间，而是将代码运行时间随数据规模增长的变化趋势表现出来。
由于公式中的低阶、常量、系数并不会左右代码运行时间的增长趋势，因此可以将它们全部忽略。
所以，上述公式又可以表示为：
加法法则
说明：程序的总复杂度等于量级最大的那段代码的复杂度
公式：
乘法法则
说明：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
公式：
常见时间复杂度分析
-
多项式量级
常量阶 O(1)
对数阶 O(logn)
线性阶 O(n)
线性对数阶 O(nlogn)
平方阶 O(n^2)
K方阶 O(n^k)
-
非多项式量级
指数阶 O(2^n)
阶乘阶 O(n!)
-
非多项式量级的算法随着数据规模n的增大，其代码执行时间会急剧增加。
O(1)
O(1)只是表示常量级时间复杂度，并不代表代只执行了一行代码。
例如下方代码的时间复杂度为O(1)，而并不是O(2)
int i = 0; int j = 1;
对数阶
-
O(logN)
-
O(NlogN)
示例：
int i = 1; while(i <= n) { i = i * 2; }
上述代码，当i小于等于n时，每循环一次代码，变量i的值就会乘以2。因此，变量i的取值为一个等比数列：
k值即为代码的循环次数，因此，根据公式
求解出
所以，这段代码的时间复杂度为
将上面的代码进行稍微的修改：
int i = 1; while(i <= n) { i = i * 5; }
根据之前推论，这段代码的的时间复杂度为
但是！！！这两段代码的时间复杂度都为
下面我们以
为例，进行说明。
由于对数之间是可以进行互相转换的
因此又可以转换为
所以：
在算法复杂度分析时，可以忽略常量带来的影响。
所以，
因此，在对数阶时间复杂度表示中，可以忽略其底数
将它们统一表示为
O(NlogN)则代表将时间复杂度为O(logN)的代码又运行了N遍。
空间杂度分析
空间复杂度全称为渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
每段功能完全的代码在运行过程中都会占用一些存储空间：
-
代码本身占用的空间
-
程序中输入与输出的数据所占用的空间
-
程序在运行中动态申请的空间
一般程序中动态申请的空间，对空间复杂度的影响最大。
int n; scanf("%d", &n); int a[10];
上述代码在运行时所申请的空间并不会随着n的增大而增大。
因此该段代码的空间复杂度为O(1)
将上述代码稍作修改
int n; scanf("%d", &n); int a[n];
则该段代码的空间复杂度与n有关，记为O(n)
一般常见的空间复杂度为O(1)、O(n)、O(n )。
下载文档
