关闭

轻松搞定时间复杂度

时间: 2019-04-30阅读: 667标签: 算法

通过学习本文,你可以掌握以下三点内容:

为什么需要时间复杂度;
时间复杂度怎么表示;
怎样分析一段代码的时间复杂度


相信认真阅读过本文,面对一些常见的算法复杂度分析,一定会游刃有余,轻松搞定。文章中举的例子,也尽量去贴近常见场景,难度递增。

复杂度是用来衡量代码执行效率的指标,直白讲代码的执行效率就是一段代码执行所需要的时间。

那么,有人会问了,代码执行所需要的时间,我执行一下,看看用了多少时间不就可以了?还要时间复杂度干啥?


一、为什么需要时间复杂度

实际开发时,我们希望自己的代码是最优的,但总不能把所有的实现的方式都写出来,再跑一遍代码做比较,这样不太实际,所以需要一个指标可以衡量算法的效率。
而且,直接跑代码看执行时间会有一些局限性:


1.测试结果受当前运行环境影响

同样的代码在不同硬件的机器上进行测试,得到的测试结果明显会不同。有时候同样是a,b两段代码,在x设备上,a执行的速度比b快,但到了y设备上,可能会完全相反的结果。


2.测试结果受测试数据的影响

不同的测试数据可能会带来不同的结果,比如我们采用顺序查找的方法查找数组中的一个元素,如果这个元素刚好在数组的第一位,执行一次代码就能找到,而如果要找的元素位于数组最后,就要遍历完整个数组才能得到结果。

于是乎,我们需要一个不受硬件,宿主环境和数据集影响的指标来衡量算法的执行效率,它就是算法的复杂度分析。


二、时间复杂度怎么表示

我们知道了为什么需要时间复杂度,那要怎么来表示它呢?下面通过一个简单例子,来说明一下 大O时间复杂度表示法。 首先看第一个例子:

function factorial(){
   let i = 0 // 执行了1次
   let re = 1 // 执行了1次
   for(;i < n; i++ ){ // 执行了n次
       re*= n // 执行了n次
   }
   return re // 执行了1次
}

上面代码是求n的阶乘(n!)的方法,即n×...×3×2×1

我们粗略的计算一下这段代码的执行时间。 首先,为了方便计算,假设执行每行代码的执行时间是相同的。 在这里,假设每行代码执行一次的时间设为t,代码的总执行时间为T(n)。 代码的第2行,第3行执行了一次,需要的时间是t + t = 2t; 代码的第4行,第5行都执行了n次,所以用时(n + n)t = 2n*t; 代码的第7行,只执行了一次,需要时间 t。

所以执行这段代码的总时间是:

T(n) = 2t + 2nt + t = (2n + 3)t

我们以n为x轴,T(n)为y轴,绘制出坐标图如下:


很明显,代码的总执行时间和每行代码执行的次数成正比。大O时间复杂度表示法就是用来表示来这样的趋势。 大O表示法表示代码执行时间随数据规模增长的变化趋势 下面是大O表示法的公式:

  T(n) = O(F(n))
n: 代表数据规模, 相当于上面例子中的n
F(n):表示代码执行次数的总和,代码执行次数的总和与数据规模有关,所以用F(n)表示, F(n)对应上面例子中的(2n+3)
T(n):代表代码的执行时间,对应上面例子中的T(n)
O: 大O用来表示代码执行时间T(n) 与 代码执行次数总和F(n)之间的正比关系。

现在已经知道了大O表示法公式的含义,我们尝试着把上面例子得出的公式改写成大O表示法,结果如下:

T(n) = O(2n + 3)

上面已经说过,大O表示法表示代码执行时间随数据规模增长的变化趋势,只是表示趋势,而不是代表实际的代码执行时间, 当公式中的n无穷大时,系数和常数等对趋势造成的影响就会微乎其微,可以忽略,所以,忽略掉系数和常数,最终上面例子简化成如下的大O表示法:

T(n) = O(n)

至此,我们已经知道了什么是大O表示法以及如何使用大O表示法来表示时间复杂度,下面我们利用上面的知识,来分析下面代码的时间复杂度。

  function reverse(arr){
      let n = arr.length // 执行了1次
      let i = 0 // 执行了1次
      for(;i<n-1;i++){ // 执行了n次
          let j = 0 // 执行了n次
          for(j=0;j<n-1;j++){ // 执行了n²次
              var temp=arr[j] // 执行了n²次
              arr[j]=arr[j+1] // 执行了n²次
              arr[j+1]=temp // 执行了n²次
         }
      }
  }

这段代码的目的是颠倒数组中元素的顺序 (代码只是为了方便我们讲解用,不需要考虑代码是否最优),按照之前的分析方法分析,依然设每行代码执行时间为t,代码执行的总时间为T(n)。 第2,3行代码只执行了1次,需要时间2t; 第4,5行代码执行了n次,需要时间 2n*t 第6,7,8,9行代码执行了n²次 所以,执行这段代码的总时间:

T(n) = (4n² + 2n + 2)t

去除低阶,系数和常数,最终使用大O表示法表示为:

T(n) = O(n²)

通过上面两个例子,我们可以总结出用大O表示法表示时间复杂度的一些规律:

1. 不保留系数 
 2. 只保留最高阶 
 3. 嵌套代码的复杂度内外代码复杂度的乘积  


三、如何快速分析一段代码的时间复杂度

我们上面总结出了大O表示法的特点,只保留最高阶,所以在分析代码的时间复杂度时,我们只需要关心代码执行次数最多的代码,其他的都可以忽略。 还是看我们上面reverse的例子,执行次数最多的是代码的6,7,8,9行,执行了n²次,我们就可以很容易计算出它的复杂度为大O(n²),这个方法同样适用于存在判断条件的代码。下面是一段带条件判断语句的代码:

  function test(n){
      let res = 0
      if(n > 100){
          const a = 1
          const b = 100
          res = (a + b)*100/2
      }else {
          let i = 1
          for(;i<n; i++){
              res+=i
          }
      }
      return res
  }

这段代码的含义是,当n > 100时, 直接返回1-100的和,n < 100时,返回1到n的和。 如果按照n的大小分开分析,当n > 100时,代码的执行时间不随 n 的增大而增长,其时间复杂度记为:

T(n) = O(1)

当n <= 100时,时间复杂度为:

T(n) = O(n)

上面n > 100的情况,是最理想的情况,这种最理想情况下执行代码的复杂度称为最好情况时间复杂度; n < 100时,是最坏的情况,在这种最糟糕的情况下执行代码的时间复杂度称为最坏情况时间复杂度。 后面我们会有单独的文章来分析最好情况时间复杂度,最坏时间复杂度,平均情况时间复杂度, 均摊时间复杂度。

除了特别说明,我们所说的时间复杂度都是指的最坏情况时间复杂度,因为只有在最坏的情况下没有问题,我们对代码的衡量才能有保证。所以我们这种情况,我们依然只需要关注执行次数最多的代码,本例子的时间复杂度为O(n)。

为了方便我们确定哪段代码在计算时间复杂度中占主导地位,熟悉常见函数的时间复杂度对比情况十分必要。


四、常见的时间复杂度

最常见的时间复杂度有常数阶O(1),对数阶O(logn),线性阶O(n),线性对数阶O(nlogn),平方阶O(n²) 从下图可以清晰的看出常见时间复杂度的对比:


O(1) < O(logn) < O(n) < O(nlogn) < O(n^2)

这些常见的复杂度,其中常数阶O(1),线性阶O(n),平方阶O(n²)对我们来说已经不陌生了,在上文的例子中我们已经认识了他们,只有O(logn)还比较陌生,从图中可见对数阶的时间复杂度仅次于常数阶,可以说是性能非常好了。下面就看一个复杂度是对数阶的例子:

  function binarySearch(arr,key){
      const n = arr.length
      let low = 0
      let high = n - 1
      let mid = Math.floor((low + high) / 2)
      while (low <= high) {
          mid = Math.floor((low + high) / 2)
          if (key === arr[mid]) {
              return mid
          } else if (key < arr[mid]) {
              high = mid - 1
          } else {
              low = mid + 1
          }
      }
      return -1
  }

这是二分查找查找的代码,二分查找是一个比较高效的查找算法。 现在,我们就分析下二分查找的时间复杂度。 这段代码中执行次数最多的是第7行代码,所以只需要看这段代码的执行次数是多少。上面已经说过,我们现在考虑的都是最坏情况下的时间复杂度,那么对于这段代码,最坏的情况就是一直排除一半,直到只剩下一个元素时才找到结果,或者要找的数组中不存在要找的元素。
现在已知,每次循环都会排除掉1/2不适合的元素,假设执行第T次后,数组只剩余1个元素。
那么:
第1次执行后,剩余元素个数 n/2
第2次执行后,剩余元素个数 n/2/2 = n/4
第3次执行后,剩余元素个数 n/2/2/2 = n/8
... ...
第n次执行后,剩余元素个数 n/(2^T) = 1

由公式 n/(2^T) = 1 可得 2^T = n, 所以总次数等于 log2n,使用大O表示法,省略底数,就是O(logn)

到这里为止,一段简单的代码时间复杂度就可以分析出来了。

更复杂的时间复杂度分析,以及最好情况、最坏情况、平均情况、均摊时间复杂度,将在后面文章中介绍。


关注公众号「前端小苑」,阅读 时间复杂度详解全文  


站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

链接: http://www.fly63.com/article/detial/3136

关闭

Js排列组合的实现

犹记得高中数学,组合表示C(m, n),意思为从集合m,选出n个数生成一项,总共有多少个项的可能?组合是无序的,排列是有序的。所以排列的项数量多于组合

Js加密算法_Base64

首先有个小Tips,1个字母字符 = 1个字节(byte) = 8位(bit),这是表示单位.Base64是网络上最常见的用于传输 8bit 的编码方式之一,Base64就是一种基于64个可打印字符来表示二进制数据的方法。

PHP 迁移 Mcrypt 至 OpenSSL 加密算法详解

对称加解密算法中,当前最为安全的是 AES 加密算法(以前应该是是 DES 加密算法),PHP 提供了两个可以用于 AES 加密算法的函数簇:Mcrypt 和 OpenSSL。其中 Mcrypt 在 PHP 7.1.0 中被 Deprecated,在 PHP 7.2.0 中被移除,所以即可起你应该使用 OpenSSL 来实现 AES 的数据加解密。

js实现快速排序算法的2种方式

通过两个for循环,每一次对比相邻两个数据的大小,小的排在前面,如果前面的数据比后面的大就交换这两个数的位置,这个方法就是比较次数太多了,效率比较低。

React 中 Virtual DOM 与 Diffing 算法的关系

Virtual DOM 是一种编程理念。UI 信息被特定语言描述并保存到内存中,再通过特定的库,例如 ReactDOM 与真实的 DOM 同步信息。这一过程成为 协调 (Reconciliation)。上述只是 协调算法

Js实现首字母大写

一小段字母文本可以手动输入进行字母大小写的改变,如果是一大段文本只好借助程序来实现,中字母大小写转换是基本功能。 返回一个字符串,确保字符串的每个单词首字母都大写,其余部分小写

js生成guid

全局唯一标识符(GUID,Globally Unique Identifier)也称作 UUID(Universally Unique IDentifier) 。GUID是一种由算法生成的二进制长度为128位的数字标识符。GUID 的格式为“xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx”

原生Js获取数组中最长的连续数字序列的方法

给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。

JavaScript 实现归并排序

在本文中,我们学习 Merge Sort 背后的逻辑,并用 JavaScript 实现。最后,在空间和时间复杂度方面将归并排序与其他算法进行比较。

原生JS找出所有的水仙花数

一个三位的整数,个、十、百的立方和等于该整数(例:153=1*1*1+5*5*5+3*3*3),步骤构思:1、依次循环遍历输出所有三位数,取整,2、设置条件判断

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!