原文链接 点击查看

5个G的计算机，电子专业书籍分享。
链接：https://pan.baidu.com/s/1y8BnUlGmiJMujLlTyrhznA
提取码：j9na

在数据结构与算法的学习过程中，如果只学会了其特点，用法，而并没有掌握算法复杂度的分析，那就相当于只学会了皮毛，而没有掌握其灵魂。

由于算法复杂度的分析较为重要，该部分会分为两篇文章：今天会介绍怎么分析算法复杂度，以及常见的复杂度分析。

首先会教大家怎么去***分析算法复杂度***，算法复杂度主要有两类：

• 时间复杂度
• 空间复杂度

算符复杂度的表示一般采用***大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
• 这段代码总的运行时间为

( 2 n 2 + 2 n + 3 ) ∗ t (2n^2 + 2n + 3) * t (2n2+2n+3)∗t

由上述代码可知，一段代码的运行时间T(n)与每行代码的执行次数n成正比，则T(n) = O(f(n))。

将上述代码的运行时间代入公式得：

T ( n ) = O ( ( ( 2 n 2 + 2 n + 3 ) ∗ t ) ) T(n) = O(((2n^2 + 2n + 3) * t)) T(n)=O(((2n2+2n+3)∗t))

，这便是***大O时间复杂度表示法***。

该表示法并非表示代码的运行时间，而是将代码运行时间随数据规模增长的变化趋势表现出来。

由于公式中的低阶、常量、系数并不会左右代码运行时间的增长趋势，因此可以将它们全部忽略。
所以，上述公式又可以表示为：

T ( n ) = O ( n 2 ) T(n) = O(n^2) T(n)=O(n2)

加法法则

说明：程序的总复杂度等于量级最大的那段代码的复杂度

公式：

T ( n ) = m a x ( O ( f ( n ) ) , O ( g ( n ) ) ) = O ( m a x ( f ( n ) , g ( n ) ) ) T(n) = max(O(f(n)), O(g(n))) = O(max(f(n), g(n))) T(n)=max(O(f(n)),O(g(n)))=O(max(f(n),g(n)))

乘法法则

说明：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

公式：

T ( n ) = O ( f ( n ) ) ∗ O ( g ( n ) ) = O ( f ( n ) ∗ g ( n ) ) T(n)=O(f(n))*O(g(n))=O(f(n)*g(n)) T(n)=O(f(n))∗O(g(n))=O(f(n)∗g(n))

常见时间复杂度分析

• 多项式量级

常量阶 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( l o g N log_N logN​)
• O(N l o g N log_N logN​)

示例：

int i = 1;
while(i <= n) {
  i = i * 2;
}

上述代码，当i小于等于n时，每循环一次代码，变量i的值就会乘以2。因此，变量i的取值为一个等比数列：

n = 2 0 2 1 2 2 . . . . . . 2 k n = 2^0\quad 2^1\quad 2^2\quad......\quad 2^k n=202122......2k

k值即为代码的循环次数，因此，根据公式

2 k = n 2^k = n 2k=n

求解出

k = l o g 2 n k = log_2n k=log2​n

所以，这段代码的时间复杂度为

O ( l o g 2 N ) O(log_2N) O(log2​N)

将上面的代码进行稍微的修改：

int i = 1;
while(i <= n) {
  i = i * 5;
}

根据之前推论，这段代码的的时间复杂度为

O ( l o g 5 N ) O(log_5N) O(log5​N)

但是！！！这两段代码的时间复杂度都为

O ( l o n g N ) O(long_N) O(longN​)

下面我们以 O ( l o g 5 N ) O(log_5N) O(log5​N)为例，进行说明。

由于对数之间是可以进行互相转换的，因此 O ( l o g 5 N ) O(log_5N) O(log5​N)又可以转换为

O ( l o g 5 2 ∗ l o g 2 N ) O(log_52 * log_2N) O(log5​2∗log2​N)

因此，

O ( l o g 5 N ) = O ( C ∗ l o g 2 N ) ( c 为 常 量 ) O(log_5N) = O(C*log_2N)(c为常量) O(log5​N)=O(C∗log2​N)(c为常量)

。在算法复杂度分析时，可以忽略常量带来的影响。
所以，

O ( l o g 5 N ) = O ( l o g 2 N ) O(log_5N) = O(log_2N) O(log5​N)=O(log2​N)

因此，在对数阶时间复杂度表示中，可以忽略其底数，将它们统一表示为

O ( l o n g N ) O(long_N) O(longN​)

。

O ( N l o n g N ) O(Nlong_N) O(NlongN​)则代表将时间复杂度为 O ( l o n g N ) O(long_N) O(longN​)的代码又运行了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 )，

关注v-x-公-众-号：【嵌入式基地】
后-台-回-复：【电赛】 即可获资料
回复【编程】即可获取
包括有：C、C++、C#、JAVA、Python、JavaScript、PHP、数据库、微信小程序、人工智能、嵌入式、Linux、Unix、QT、物联网、算法导论、大数据等资料