时间复杂度和大O表示法

专注于编程、互联网动态。最终将总结的技术、心得、经验（数据结构与算法、源码分析等）享给大家，这里不只限于技术！还有职场心得、生活感悟、以及面经。点击上方 "程序员小乐" ，关注公众号，第一时间送达！

每日英文 

No matter when you start, it is important that you do not stop after starting. No matter when you end, it is more important that you do not regret after ended.

不论你在什么时候开始，重要的是开始之后就不要轻言放弃；不论你在什么时候结束，重要的是结束之后就不要后悔。

乐乐有话说 

人生有两种境界，一种是痛而不言，另一种是笑而不语。

来自：我是一只香脆的大鸡排

链接：http://www.dajipai.cc/archives/2bce0d61.html

封面来自网络

00 前言  

到今天为止，可能我们的确不会自己再去经常编写一个高效的算法。因为在各大框架或语言原生的API里，它们已经帮业务开发的程序员将最优的算法都实现了。所以我们很少用到在实际场景中，特别是作为大前端开发人员更加很少接触到。但是无论从计算机编程基础、以及编写更优秀的性能代码，这块的知识是仍然是非常重要的。

01 基础与流行  

人的一生是有限的，个人认为在编程技术栈中的学习即是一种投资行为。做我们这行的行业积累是会过期的。所以我将技术知识粗略的划分为两块。
即：基础编程知识流、流行编程知识流。
基础知识是牢固而不容易过期的，而流行编程知识往往是偏向前沿技术而活泼不稳定的，把时间轴拉长来看，新技术是不断的被迭代的。

也就是说如果我们把 sql、算法、编程思想 …归结为基础编程知识来看。java语言、kotlin语言、android、React …这种知识是当前流行编程知识流。

那么流行知识是一个反复学习新技术，不断的扔掉成旧知识的一个过程。而恰恰相反，基础知识是不会和新技术产生冲突交集的。所以如果你是一个刚刚入行不久的攻城狮，那么从投资的角度来看，我建议对基础编程知识的前期投资是越丰厚越好，而且是稳赚不陪的卖买。

正式开发环境中很多时候是飞机大炮造到一半，发现零件的质量不够好。框架子搞了一堆再牛逼，却写不出好东西或则说无法发挥最大的性能。

用优质的代码解决硬件成本

简单来说，就是如果你代码的执行算法太慢，将导致需要用硬件来撑起运行速度。这就是在过多的消耗硬件成本。而作为行业内人员或者boss，你是愿意将刀刃(钱)用在优秀的工程师上，还是高昂价格的机器上。相信这个问题，我只需要提出,你就已经有了结论。我不作过多的阐述。

02 概念  

我们今天只弄明白两点，到底什么是算法时间复杂度？什么是大O表示法？

2.1 算法时间复杂度

好，怎么理解？一句话来说就是

你用代码做某一件事件，所消耗的总体时间长度,就是该事件(算法)的时间复杂度。
这里暂且不说平均复杂度和实际复杂度。我们后面再讲这些。

2.2 大O表示法

大O表示法呢？

一个用来表示算法时间复杂度的公式名称，用于指出该算法的效率有多快。在计算机领域我们用函数来表示
当我第一次接触到大O表示法时，我还在纠结，那小o表示法又是什么。其实根本没有这种东西。大O表示法仅仅是一个名称。

//表达式其中n表示要执行的次数。
 O(n)

03 例子  

• O(n) 傻找算法(线性时间)

• O(log n) 二分查找

黑魔法大鸡排把你的老婆抓起来藏在召唤师峡谷的地窖中。依照你过人的聪明智慧，你用敏锐的嗅觉一路上根据老婆的味道，靠鼻子闻到了地窖。打开一看。里面有1000个和你老婆一模一样的蜡像，但其中有一个是真正的老婆。放眼望去，你并不知道哪个是你的老婆，因为他们实在太像了。由于被大鸡排下了诅咒，真正的老婆被封印了起来，只有通过真爱么么哒才能唤醒 （づ￣3￣）づ╭❤～。

3.1 O(n) 傻找算法(线性时间)

此刻你急中生智，骂道：“什么烂剧情例子,用鼻子闻到老婆的味道跟我聪明的智慧有个毛关系啊？,还tm要一个么么哒”，你只好决定一个一个亲下去。从第一个亲到最后一个。
我们用代码来表示这个过程就是：

//999个假老婆+一个真的
List<Wife> Wifes= {蜡像，蜡像，蜡像...真老婆，蜡像}；
// 我自己
 Lead myself =new Lead()；

for(i=0; i<=Wifes.length; ++i){
  boolean  resurrection =kiss(Wifes.get(i))； //么么哒唤醒
  if(resurrection ){
     Log.i(“已找到老婆他在”+i+“个,赶紧抬回家，远离召唤师峡谷”)；
     return ;
  }
}

 boolean  kiss(Wife mWife){
  //调用自己的么么哒方法 返回真假
 return myself.kiss(mWife)；
}

这个过程是我们有一个Wifes容器装下了999个蜡像和一个真正的老婆。然后myself 是自己,拥有一个kiss方法用来唤醒老婆并返回真假。这里模拟从第一个开始kiss到最后一个。当我们找到了老婆就停止一切行为。

那么我们的时间复杂度是：最多尝试1000次，即 O(n)来表示，其中n表示次数。是不是很简单。

这是最糟糕的结果，大鸡排将你的wife放在最后一个位置，你从第一个开始亲，亲到最后一个。你需要尝试1000次。但绝不会超过这个范围。当然实际情况也可能是O(1)，第一次成功了。

我们通过这个算法得到了时间复杂度公式： O(n)

3.2 O(log n) 二分查找

接着上面的列子。还记得召唤师峡谷里有个商店老爷爷吗？他说能为你打开此次寻找的天机。将所有蜡像的序号都展示出来，并且他每次都能告诉你整个区间内是否存在真正的老婆。你想了想那么我可以从中间对折拆分找呀，这样可以每次直接排除掉一半。这个过程就像：

第一次询问: 500~1000 他说不存在， 1~499那么一定存在。
第二次询问: 250~499 他说不存在， 1~249那么一定存在。
第三次询问: 125~249 他说不存在， 1~124那么一定存在。
第四次询问: 63~124 他说不存在， 1~62那么一定存在。
第五次询问: 31~62 他说不存在， 1~30那么一定存在。
第六次询问: 15~30 他说不存在， 1~15那么一定存在。
第七次询问: 7~14 他说不存在， 1~6那么一定存在。
第八次询问: 3~6 他说不存在， 1~2那么一定存在。
第九次询问: 2 他说不对，那么结果只剩下1了。

好，我们捋一捋。实际每次询问我们都可以排除一半绝对不可能存在的。也就是说最多我们需要经过9步即可完成从1000个老婆中出真正的老婆。
如果我们把它写成代码就会是这个样子：

//999个假老婆+一个真的
List<Wife> Wifes= {蜡像，蜡像，蜡像...真老婆，蜡像}；
// 我自己
 Lead myself =new Lead()；

int low=0; //最低位
int high = Wifes.length-1; //最高位
int mid; //折中猜想数

  while( low<=high){
       mid=(low+higt)/2
      likeWife=Wifes.get(mid)；
      if( kiss(likeWife)){
          Log.i(“已找到老婆他在”+mid+“个,赶紧抬回家，远离召唤师峡谷”)；
          return ;
      }
    boolean  deviation=  elderlyHelp(likeWife)；
      if(deviation){ //往左偏移 表示大了
      high=mid-1；
      }esle{  //往右偏移 表示小了
      low=mid+1；
    }
  }

}

//老爷爷的帮助 返回区间内是否包含
boolean   elderlyHelp(){
  ····
}

 boolean  kiss(Wife mWife){
  //调用自己的么么哒方法 返回真假
 return myself.kiss(mWife)；
}

这样我们就推倒出二分法查找实际是是对数函数的反向幂运算。所以推倒出公式为：O(log n)

稍微说一下log对数运算，也许你学过又忘了。log以10为底数多少次幂结果等于100，其实就是指多少个10相乘的结果为100。答案是两个：10 × 10 = 100。所以log以10为底数的 2次幂等于100。

O(n)对比 O(log n)

假定我们每一次myself.kiss用于激活的方法需要1秒钟执行。当采用第一种算法时，时间复杂度为O(n) ，那么需要1000秒才能找出老婆。但如果采用了二分查找，时间复杂度为 O(log n) ，那么仅需要9秒即可完成操作。其中n表示次数。那么由此可见O(log n) 比O(n)要快。当元素越多的时候，执行的效率就尤其具有可比性。

04 题外话  

好，那么到这里就讲完了今天的内容啦。如果你感兴趣的话可以再去了解O(n!) n阶乘的时间复杂度。当n阶越高，消耗的时间越长。这是计算机领域非常经典的旅行商问题。

看完本篇并不能让你成一个优秀的工程狮，这是入门级别的基础知识。但如果因为是你看完这篇文章后产生了这种想法，我的目的就达到了，至少已经在通往优秀工程狮的路上了。那么更多的知识还需要长久的打磨和学习。共勉 加油！

如果您觉得不错，请别忘了转发、分享、点赞让更多的人去学习， 您的举手之劳，就是对小乐最好的支持，非常感谢！

如何您想进技术群交流，关注公众号在后台回复 “加群”，或者 “学习” 即可

著作权归作者所有，欢迎大家投稿

推荐阅读

看完本文有收获？请转发分享给更多人
关注「程序员小乐」，提升技能