[嵌入式]快速掌握算法复杂度分析

原文链接 点击查看

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
• 这段代码总的运行时间为

$(2n^2+2n+3)?t$

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

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

$T(n)=O(((2n^2+2n+3)?t))$

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

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

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

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

加法法则

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

公式：

$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))$

常见时间复杂度分析

• 多项式量级

常量阶 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($lo{g}_N$)
• O(N$lo{g}_N$)

示例：

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

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

$n=2^0{2}^1{2}^2......2^k$

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

$2^k=n$

求解出

$k=lo{g}_{2}n$

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

$O(lo{g}_{2}N)$

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

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

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

$O(lo{g}_{5}N)$

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

$O(lon{g}_N)$

下面我们以$O(lo{g}_{5}N)$为例，进行说明。

由于对数之间是可以进行互相转换的，因此$O(lo{g}_{5}N)$又可以转换为

$O(lo{g}_{5}2?lo{g}_{2}N)$

因此，

$O(lo{g}_{5}N)=O(C?lo{g}_{2}N)(c为常量)$

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

$O(lo{g}_{5}N)=O(lo{g}_{2}N)$

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

$O(lon{g}_N)$

。

$O(Nlon{g}_N)$则代表将时间复杂度为$O(lon{g}_N)$的代码又运行了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、物联网、算法导论、大数据等资料