在数据结构与算法的学习过程中,如果只学会了其特点,用法,而并没有掌握算法复杂度的分析,那就相当于只学会了皮毛,而没有掌握其灵魂。
由于算法复杂度的分析较为重要,该部分会分为两篇文章:今天会介绍怎么分析算法复杂度,以及常见的复杂度分析。
首先会教大家怎么去***分析算法复杂度***,算法复杂度主要有两类:
时间复杂度
空间复杂度
算符复杂度的表示一般采用***大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;
对数阶
示例:
int i = 1; while(i <= n) { i = i * 2; }
上述代码,当i小于等于n时,每循环一次代码,变量i的值就会乘以2。因此,变量i的取值为一个等比数列:
k值即为代码的循环次数,因此,根据公式
求解出
所以,这段代码的时间复杂度为
将上面的代码进行稍微的修改:
int i = 1; while(i <= n) { i = i * 5; }
根据之前推论,这段代码的的时间复杂度为
但是!!!这两段代码的时间复杂度都为
下面我们以 为例,进行说明。
由于对数之间是可以进行互相转换的,因此又可以转换为
因此,
(c为常量)。在算法复杂度分析时,可以忽略常量带来的影响。
所以,
因此,在对数阶时间复杂度表示中,可以忽略其底数,将它们统一表示为
则代表将时间复杂度为的代码又运行了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 ),