轻松搞定时间复杂度

更新日期: 2019-04-30阅读: 2k标签: 算法

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

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


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

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

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


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

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


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)

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

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


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


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

js洗牌算法:javascript数组随机打乱顺序的实现方法

有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。

程序员必须知道的10大基础实用算法及其讲解

程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法

js从数组取出 连续的 数字_实现一维数组中连续数字分成几个连续的数字数组

使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。

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

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

Tracking.js_ js人脸识别前端代码/算法框架

racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。

JS常见算法题目

JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题

RSA算法详解

这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。

PageRank算法的定义与来源、以及PageRank算法原理

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。

js算法_js判断一个字符串是否是回文字符串

什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a

js之反转整数算法

将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。

点击更多...

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