如何理解算法的复杂度

本文主要讲解“如何理解算法的复杂性”，感兴趣的朋友不妨看看。本文介绍的方法简单、快速、实用。让边肖带你学习如何理解算法的复杂性。

1. Motivation - 为什么需要复杂度分析

事后统计(即运行一次代码，通过统计和监控得到运行时间和占用内存大小)测试结果非常依赖测试环境，受数据规模影响很大。但实际上，在没有具体测试数据的情况下，更需要估计算法的执行效率。

2. 大 O 复杂度表示法

算法的执行效率简单来说就是算法的执行时间。例如，下面代码的执行时间，假设每行代码的执行时间相同，就是unit_time。基于这个假设，这段代码的总执行时间是(2n ^ 2)* unit _ time。

int cal(intn){ int sum=0；inti=1；for(；I=n；I){ sum=sum I；} returnsum}通过这个例子可以看出，总执行时间T(n)与每行代码执行次数成正比，可以满足公式T(n)=O(f(n))，其中n是数据的大小，f(n)表示每行代码执行的总次数，O()表示函数，即T(n)与f(n)成正比。在这个例子中，T(n)=O(2n ^ 2)，这被称为具有大O复杂度的表示。但实际上，大O时间复杂度并不具体表示代码执行的真实执行时间，而是表示代码执行时间随数据规模增长的变化趋势，也称之为递进时间复杂度。那么，在2n ^ 2中，系数2和常数2不影响增长趋势，比如是线性的，也不是因为系数2或常数2改变了它的线性增长趋势，所以可以写成T(n)=O(n)。例如，如果t (n T(n)=O(n^2)，则意味着代码执行时间随数据规模n的增加的变化趋势为n平方。下图显示了不同时间复杂度下，执行时间随着数据规模的增加而变化。

3. 时间复杂度分析

如何分析一段代码的时间复杂度？可以采用以下方法。

只注意循环最多的代码。

因为大O复杂度表示只代表一种趋势，公式中的常数项、低阶和系数可以忽略，只能记录一个最大阶。因此，在分析一个算法和一段代码的复杂度时，我们只需要关注循环次数最多的那段代码。例如，在下面的代码中，时间复杂度为O(n)。

int cal(intn){ int sum=0；inti=1；for(；I=n；I){ sum=sum I；} returnsum}加法法则：总复杂度等于最大数量级的代码复杂度。

这主要是为了省略大O复杂度中的低阶项。个人觉得这个方法和上面的方法有重叠。例如，下面的代码可以根据周期分为三段。第一段有周期，但周期数是不变项，对增长趋势没有影响，因此时间复杂度为O(1)，第二段时间复杂度为O(n)，第三段时间复杂度为O(n ^ 2)。三段中时间复杂度最大的是整个代码的时间复杂度。

时间复杂度。

int cal(int n) {     int sum_1 = 0;     int p = 1;     for (; p < 100; ++p) {         sum_1 = sum_1 + p;     }      int sum_2 = 0;     int q = 1;     for (; q < n; ++q) {         sum_2 = sum_2 + q;     }      int sum_3 = 0;     int i = 1;     int j = 1;     for (; i <= n; ++i) {         j = 1;          for (; j <= n; ++j) {             sum_3 = sum_3 +  i * j;         }     }      return sum_1 + sum_2 + sum_3; }

• 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

比如下面这段代码中，f() 是一个循环操作，整个复杂度是 O(n)，而 cal() 中的循环相当于外层，调用了 f()，假如把 f()  当成一个简单的操作的话，那么时间复杂度是 O(n)，算上 f() 真实的复杂度之后，整个 cal() 的时间复杂度是 O(n)*O(n)=O(n*n) =  O(n^2)。

int cal(int n) {     int ret = 0;      int i = 1;     for (; i < n; ++i) {         ret = ret + f(i);     }  }   int f(int n) {     int sum = 0;     int i = 1;     for (; i < n; ++i) {         sum = sum + i;     }      return sum; }

3.1. 常见时间复杂度

下面针对上述的若干种时间复杂度进行阐述：

1.O(1)

O(1)是常量级时间复杂度的一种表示，只要代码的时间不随 n 的增大而增大，那么它的时间复杂也是  O(1)。一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是 O(1)。

2.O(logn)、O(nlogn)

对数时间复杂度往往比较难分析，比如下面这段代码中

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

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

O(nlogn) 的时间复杂度就相当于上面说到的“乘法法则”：一段代码的时间复杂度为O(logn) ，这段代码循环 n 次，时间复杂度就是  O(nlogn) 了。

3.O(m+n)、O(m*n)

这种情况下，代码的复杂度是由两个数据规模决定的。如下代码所示：

int cal(int m, int n) {     int sum_1 = 0;     int i = 1;     for (; i < m; ++i) {         sum_1 = sum_1 + i;     }      int sum_2 = 0;     int j = 1;     for (; j < n; ++j) {         sum_2 = sum_2 + j;     }      return sum_1 + sum_2; }

从这段代码中可以看出m 和 n 是两个数据规模，无法评估 m 和 n 的量级大小。因此，不能省略其中任何一个，所以就是 O(m+n) 了。

4.O(2^n)、O(n!)

在上述表格中列出的复杂度量级，可以粗略的分为两类：多项式量级和非多项式量级。其中非多项式量级只有这两个。非多项式量级的算法问题也叫做  NP(Non-Deterministic Ploynomial，非确定多项式)问题。当 n  越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间也会无限增长，所以是种很低效的算法。

3.2. 最好、最坏情况时间复杂度

比如下面这段代码中，是在数组中查找一个数据，但是并不是把整个数组都遍历一遍，因为有可能中途找到了就可以提前退出循环。那么，最好的情况是如果数组中第一个元素正好是要查找的变量  x ，时间复杂度就是 O(1)。最坏的情况是遍历了整个数组都没有找到想要的 x，那么时间复杂就成了 O(n)。因此 O(1)  就是这段代码的最好情况时间复杂度，也就是在最好的情况下，执行这段代码的时间复杂度。O(n) 就是这段代码的最坏情况时间复杂度。

// n表示数组array的长度 int find(int[] array, int n, int x) {     int i = 0;     int pos = -1;     for (; i < n; ++i) {         if (array[i] == x) {             pos = i;             break;         }     }     return pos; }

3.3. 平均情况时间复杂度(加权平均时间复杂度或者期望时间复杂度)

最好和最坏情况时间复杂度都是极端情况发生的时间复杂度，并不常见。因此可以使用平均情况时间复杂度来表示。比如上面这段代码中查找 x  在数组中的位置有两种情况，一种是在数组中，另一种是不在数组中。在数组中又可以在数组中的 0~n-1 位置。假设在数组中和不在数组中的概率分别为  1/2，在数组中的 0~n-1 的位置概率都一样，为 1/(2 *n)。因此，上述这段的平均情况时间复杂度(或者叫加权平均时间复杂度、期望时间复杂度)为

假如使用如下公式计算复杂度的话，那么就相当于每种情况的发生概率都是 1/(n+1) 了，没有考虑每种的情况的不同概率，存在一定不准确性。

3.4. 均摊时间复杂度

均摊时间复杂度采用的是摊还分析法(平摊分析法)。就是把耗时多的操作，平摊到其他那些时间复杂度比较低的操作上。比如下面这段代码

// array表示一个长度为n的数组 // 代码中的array.length就等于n int[] array = new int[n]; int count = 0;  void insert(int val) {     if (count == array.length) {         int sum = 0;         for (int i = 0; i < array.length; ++i) {             sum = sum + array[i];         }         array[0] = sum;         count = 1;     }      array[count] = val;     ++count; }

这段代码想要实现的就是往一个数组中插入数据，如果数组满了的话，那么就求和之后的 sum  放到数组的第一个位置，之后继续将数据插入到数组中。通过分析可以发现，这段代码的最好情况时间复杂度是 O(1)，最坏情况时间复杂度是 O(n)，平均时间复杂度是  O(1)。

那么这段代码中，在大部分情况下，时间复杂度是 O(1)，只有个别情况下，复杂度才是 O(n)。并且，O(1) 和 O(n) 出现的比较规律，一般一个  O(n) 执行之后，会出现 n-1 个 O(1) 的执行。针对这种情况，可以使用摊还分析法，就是把 O(n) 这个耗时多的时间复杂度均摊到接下来的 n-1 个  O(1) 的执行上，均摊下来的时间复杂度为 O(1)，这个时间复杂度就是均摊时间复杂度。

那么均摊时间复杂度不怎么常见，常见的场景是：对一个数据结构进行一组连续操作，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高。而且这些操作之间存在前后连贯的时序关系，比如上面提到的先是一系列  O(1) 的时间复杂度操作，接下来是 O(n)  的时间复杂度操作。这个时候就可以采用摊还分析法将较高时间复杂度的那次操作的耗时平摊到其他时间复杂度比较低的操作上。

一般均摊时间复杂度等于最好情况时间复杂度。那么如何区别平均时间复杂度和均摊时间复杂度呢?我觉得看你使用哪种方法，假如使用摊还分析法算出来的时间复杂度就是均摊时间复杂度，使用加权方式、或者期望值计算方式算出来的时间复杂度就是平均时间复杂度。

4. 空间复杂度分析

空间复杂度分析方法很简单。时间复杂度的全称叫做渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。那么空间复杂度全称叫做渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。

比如下面这段代码中，首先 int i= 0; 申请一个空间存储变量，是常量可以忽略，int[] a = new int[n]; 申请了一个大小为 n 的  int 类型数组，剩下的代码都没有占用更多的空间，因此空间复杂度是 O(n)

void print(int n) {     int i = 0;     int[] a = new int[n];     for (i; i <n; ++i) {         a[i] = i * i;     }      for (i = n-1; i >= 0; --i) {         print out a[i]     } }

对于空间复杂度分析，其实比较简单，一般看变量声明时分配的空间大小即可。

4.1. 常用时间复杂度

常用的空间复杂度就上面 3 种，O(nlogn)、O(logn)这样的对数阶复杂度一般都用不到。

5. 总结

回顾一下复杂度分析，总的来说时间复杂度的 motivation 是我们想要一个不用具体数据就可以估算出算法的执行效率的方法。而时间复杂度采用的是大 O  表示法，大 O 表示法其实描述的是一个增长趋势。比如 n^2 中，当 n 的值越来越大时候，O(n^2) 这个算法的执行时间是成平方增长的，而 O(n)  这个算法的执行时间是成直线型增长的，因此 O(n^2)  的时间复杂度是更高(见第一张图)。之后是几种常用的时间复杂度，平均时间复杂度、最好最坏时间复杂度，均摊时间复杂度(均摊这种思想在操作系统中有一定的体现：RR  调度算法中，在时间片大小选择上，有着类似的处理方式，因为 RR  是一个抢占式调度算法，当发生调度之后会发生进程的上下文切换，而进程的上下文切换是需要额外的时间成本，而这个时间成本会均摊到时间片上，当时间片很大时，显然均摊的效果不错，因此这个额外的时间成本影响会很小)

为什么说掌握时间复杂度是掌握了根本大法?去年上课的时候，记忆比较深刻的是老师好像在讲一个比较难的算法问题，然后从最简单、复杂度最高的解法开始讲起，然后跟带着我们一步一步分析每一块代码的时间复杂度，然后说这块的代码的时间复杂度是  O(n^2)，我们能不能想办法把它给降下来的呢?然后就在那思考了怎么降了，一句一句代码看过去，画图等等，最终将时间复杂度降下来了。因此个人觉得掌握时间复杂度分析之后，掌握的是算法的分析方法，你可以分析出每段代码的复杂度，然后通过思考最终把相应代码的时间复杂度降下来。假如你复杂度分析掌握不熟，那么怎么降都不知道，那么算法的优化也就没了。

到此，相信大家对“如何理解算法的复杂度”有了更深的了解，不妨来实际操作一番吧！这里是网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！