现在是伟大美好的端午佳节时间，你是在回家的路上吗？祝各位简友们生日快乐！！！啪啪啪！ 又调皮，明明是中秋节快乐好咩~。
今日有酒尽早醉，明日无酒老夫我开盖再来一瓶。 咱今天扒一下软件编程中的算法时间复杂度。
“玛德，智 ........勇双全。一说算法之类的东西晚生我就想打哈欠，犯困。(o-ωｑ)).oO ”
“是不是感觉老有知识咳不出来，又咽不下去？老夫反手就是一张过去的CD，听听那是我们的XX”
“巴拉拉能量，麻辣割鸡小魔仙全身变。kuang！别担心，大鸡排今天讲的足够简单、 粗暴不戴X，易理解。” 快坐上来吧，搞起。搞起。
目录
- 前言
- 概念
- 例子
- 题外话
前言
到今天为止，可能我们的确不会自己再去经常编写一个高效的算法。因为在各大框架或语言原生的API里，它们已经帮业务开发的程序员将最优的算法都实现了。所以我们很少用到在实际场景中，特别是作为大前端开发人员更加很少接触到。但是无论从计算机编程基础、以及编写更优秀的性能代码，这块的知识是任然是非常重要的。
基础与流行
人的一生是有限的，个人认为在编程技术栈中的学习即是一种投资行为。做我们这行的行业积累是会过期的。所以我将技术知识粗略的划分为两块。
即：基础编程知识流、流行编程知识流。
基础知识是牢固而不容易过期的，而流行编程知识往往是偏向前沿技术而活泼不稳定的，把时间轴拉长来看，新技术是不断的被迭代的。
也就是说如果我们把 sql、算法、编程思想 ...归结为基础编程知识来看。java语言、kotlin语言、android、React ...这种知识是当前流行编程知识流。
那么流行知识是一个反复学习新技术，不断的扔掉成旧知识的一个过程。而恰恰相反，基础知识是不会和新技术产生冲突交集的。所以如果你是一个刚刚入行不久的攻城狮，那么从投资的角度来看，我建议对基础编程知识的前期投资是越丰厚越好，而且是稳赚不陪的卖买。
正式开发环境中很多时候是飞机大炮造到一半，发现零件的质量不够好。框架子搞了一堆再牛逼，却写不出好东西或则说无法发挥最大的性能。
用优质的代码解决硬件成本
简单来说，就是如果你代码的执行算法太慢，将导致需要用硬件来撑起运行速度。这就是在过多的消耗硬件成本。而作为行业内人员或者boss，你是愿意将刀刃(钱)用在优秀的工程师上，还是高昂价格的机器上。相信这个问题，我只需要提出,你就已经有了结论。我不作过多的阐述。
概念
我们今天只弄明白两点，到底什么是算法时间复杂度？什么是大O表示法？
算法时间复杂度
好，怎么理解？一句话来说就是
你用代码做某一件事件，所消耗的总体时间长度,就是该事件(算法)的时间复杂度。
这里暂且不说平均复杂度和实际复杂度。我们后面再讲这些。
大O表示法
大O表示法呢？
一个用来表示算法时间复杂度的公式名称，用于指出该算法的效率有多快。在计算机领域我们用函数来表示
当我第一次接触到大O表示法时，我还在纠结，那小o表示法又是什么。其实根本没有这种东西。大O表示法仅仅是一个名称。
//表达式其中n表示要执行的次数。
O(n)
例子
- O(n) 傻找算法(线性时间)
- O(log n) 二分查找
黑魔法大鸡排把你的老婆抓起来藏在召唤师峡谷的地窖中。依照你过人的聪明智慧，你用敏锐的嗅觉一路上根据老婆的味道，靠鼻子闻到了地窖。打开一看。里面有1000个和你老婆一模一样的蜡像，但其中有一个是真正的老婆。放眼望去，你并不知道哪个是你的老婆，因为他们实在太像了。由于被大鸡排下了诅咒，真正的老婆被封印了起来，只有通过真爱么么哒才能唤醒 （づ￣3￣）づ╭❤～。
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)
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)要快。当元素越多的时候，执行的效率就尤其具有可比性。
题外话
好，那么到这里就讲完了今天的内容啦。如果你感兴趣的话可以再去了解O(n!) n阶乘的时间复杂度。当n阶越高，消耗的时间越长。这是计算机领域非常经典的旅行商问题。 感兴趣戳这里过去继续深入阅读。
旅行推销员问题（英语：Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。
看完本篇并不能让你成一个优秀的工程狮，这是入门级别的基础知识。但如果因为是你看完这篇文章后产生了这种想法，我的目的就达到了，至少已经在通往优秀工程狮的路上了。那么更多的知识还需要长久的打磨和学习。共勉 加油！
如何下次找到我?
- 关注我的简书
- 本篇同步Github仓库:https://github.com/BolexLiu/MyNote (可以关注)
网友评论