現(xiàn)在是偉大美好的端午佳節(jié)時(shí)間初坠，你是在回家的路上嗎？祝各位簡(jiǎn)友們生日快樂(lè)Ｅ砦怼５獭！啪啪啪冠跷！ 又調(diào)皮南誊，明明是中秋節(jié)快樂(lè)好咩~身诺。
今日有酒盡早醉蜜托，明日無(wú)酒老夫我開(kāi)蓋再來(lái)一瓶。 咱今天扒一下軟件編程中的算法時(shí)間復(fù)雜度霉赡。
“瑪?shù)麻衔瘢?........勇雙全。一說(shuō)算法之類(lèi)的東西晚生我就想打哈欠穴亏，犯困蜂挪。(o-ωｑ)).oO ”
“是不是感覺(jué)老有知識(shí)咳不出來(lái)，又咽不下去嗓化？老夫反手就是一張過(guò)去的CD棠涮，聽(tīng)聽(tīng)那是我們的XX”
“巴拉拉能量，麻辣割雞小魔仙全身變刺覆。kuang严肪！別擔(dān)心，大雞排今天講的足夠簡(jiǎn)單、 粗暴不戴X驳糯，易理解篇梭。” 快坐上來(lái)吧酝枢，搞起恬偷。搞起。
目錄
- 前言
- 概念
- 例子
- 題外話
前言
到今天為止帘睦，可能我們的確不會(huì)自己再去經(jīng)常編寫(xiě)一個(gè)高效的算法袍患。因?yàn)樵诟鞔罂蚣芑蛘Z(yǔ)言原生的API里，它們已經(jīng)幫業(yè)務(wù)開(kāi)發(fā)的程序員將最優(yōu)的算法都實(shí)現(xiàn)了竣付。所以我們很少用到在實(shí)際場(chǎng)景中协怒，特別是作為大前端開(kāi)發(fā)人員更加很少接觸到。但是無(wú)論從計(jì)算機(jī)編程基礎(chǔ)卑笨、以及編寫(xiě)更優(yōu)秀的性能代碼孕暇，這塊的知識(shí)是任然是非常重要的。
基礎(chǔ)與流行
人的一生是有限的赤兴，個(gè)人認(rèn)為在編程技術(shù)棧中的學(xué)習(xí)即是一種投資行為妖滔。做我們這行的行業(yè)積累是會(huì)過(guò)期的。所以我將技術(shù)知識(shí)粗略的劃分為兩塊桶良。
即：基礎(chǔ)編程知識(shí)流座舍、流行編程知識(shí)流。
基礎(chǔ)知識(shí)是牢固而不容易過(guò)期的陨帆，而流行編程知識(shí)往往是偏向前沿技術(shù)而活潑不穩(wěn)定的曲秉，把時(shí)間軸拉長(zhǎng)來(lái)看，新技術(shù)是不斷的被迭代的疲牵。
也就是說(shuō)如果我們把 sql承二、算法、編程思想 ...歸結(jié)為基礎(chǔ)編程知識(shí)來(lái)看纲爸。java語(yǔ)言亥鸠、kotlin語(yǔ)言、android识啦、React ...這種知識(shí)是當(dāng)前流行編程知識(shí)流负蚊。
那么流行知識(shí)是一個(gè)反復(fù)學(xué)習(xí)新技術(shù)，不斷的扔掉成舊知識(shí)的一個(gè)過(guò)程颓哮。而恰恰相反家妆，基礎(chǔ)知識(shí)是不會(huì)和新技術(shù)產(chǎn)生沖突交集的。所以如果你是一個(gè)剛剛?cè)胄胁痪玫墓コ仟{冕茅，那么從投資的角度來(lái)看伤极，我建議對(duì)基礎(chǔ)編程知識(shí)的前期投資是越豐厚越好腰鬼，而且是穩(wěn)賺不陪的賣(mài)買(mǎi)。
正式開(kāi)發(fā)環(huán)境中很多時(shí)候是飛機(jī)大炮造到一半塑荒，發(fā)現(xiàn)零件的質(zhì)量不夠好熄赡。框架子搞了一堆再牛逼齿税，卻寫(xiě)不出好東西或則說(shuō)無(wú)法發(fā)揮最大的性能彼硫。
用優(yōu)質(zhì)的代碼解決硬件成本
簡(jiǎn)單來(lái)說(shuō)，就是如果你代碼的執(zhí)行算法太慢凌箕，將導(dǎo)致需要用硬件來(lái)?yè)纹疬\(yùn)行速度拧篮。這就是在過(guò)多的消耗硬件成本。而作為行業(yè)內(nèi)人員或者boss牵舱，你是愿意將刀刃(錢(qián))用在優(yōu)秀的工程師上串绩，還是高昂價(jià)格的機(jī)器上。相信這個(gè)問(wèn)題芜壁，我只需要提出,你就已經(jīng)有了結(jié)論礁凡。我不作過(guò)多的闡述。
概念
我們今天只弄明白兩點(diǎn)慧妄，到底什么是算法時(shí)間復(fù)雜度顷牌？什么是大O表示法？
算法時(shí)間復(fù)雜度
好塞淹，怎么理解窟蓝？一句話來(lái)說(shuō)就是
你用代碼做某一件事件，所消耗的總體時(shí)間長(zhǎng)度,就是該事件(算法)的時(shí)間復(fù)雜度饱普。
這里暫且不說(shuō)平均復(fù)雜度和實(shí)際復(fù)雜度运挫。我們后面再講這些。
大O表示法
大O表示法呢套耕？
一個(gè)用來(lái)表示算法時(shí)間復(fù)雜度的公式名稱(chēng)谁帕，用于指出該算法的效率有多快。在計(jì)算機(jī)領(lǐng)域我們用函數(shù)來(lái)表示
當(dāng)我第一次接觸到大O表示法時(shí)箍铲，我還在糾結(jié)雇卷，那小o表示法又是什么鬓椭。其實(shí)根本沒(méi)有這種東西颠猴。大O表示法僅僅是一個(gè)名稱(chēng)。
//表達(dá)式其中n表示要執(zhí)行的次數(shù)小染。
O(n)
例子
- O(n) 傻找算法(線性時(shí)間)
- O(log n) 二分查找
黑魔法大雞排把你的老婆抓起來(lái)藏在召喚師峽谷的地窖中翘瓮。依照你過(guò)人的聰明智慧，你用敏銳的嗅覺(jué)一路上根據(jù)老婆的味道裤翩，靠鼻子聞到了地窖资盅。打開(kāi)一看调榄。里面有1000個(gè)和你老婆一模一樣的蠟像，但其中有一個(gè)是真正的老婆呵扛。放眼望去每庆，你并不知道哪個(gè)是你的老婆，因?yàn)樗麄儗?shí)在太像了今穿。由于被大雞排下了詛咒缤灵，真正的老婆被封印了起來(lái)，只有通過(guò)真愛(ài)么么噠才能喚醒 （づ￣3￣）づ╭?～蓝晒。
O(n) 傻找算法(線性時(shí)間)
此刻你急中生智腮出，罵道：“什么爛劇情例子,用鼻子聞到老婆的味道跟我聰明的智慧有個(gè)毛關(guān)系啊芝薇？,還tm要一個(gè)么么噠”胚嘲，你只好決定一個(gè)一個(gè)親下去。從第一個(gè)親到最后一個(gè)洛二。
我們用代碼來(lái)表示這個(gè)過(guò)程就是：
//999個(gè)假老婆+一個(gè)真的
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+“個(gè),趕緊抬回家君珠，遠(yuǎn)離召喚師峽谷”)；
return ;
}
}
boolean kiss(Wife mWife){
//調(diào)用自己的么么噠方法 返回真假
return myself.kiss(mWife)娇斑；
}
這個(gè)過(guò)程是我們有一個(gè)Wifes容器裝下了999個(gè)蠟像和一個(gè)真正的老婆策添。然后myself 是自己,擁有一個(gè)kiss方法用來(lái)喚醒老婆并返回真假。這里模擬從第一個(gè)開(kāi)始kiss到最后一個(gè)毫缆。當(dāng)我們找到了老婆就停止一切行為唯竹。
那么我們的時(shí)間復(fù)雜度是：最多嘗試1000次，即** O(n)來(lái)表示苦丁，其中n**表示次數(shù)浸颓。是不是很簡(jiǎn)單。
這是最糟糕的結(jié)果旺拉，大雞排將你的wife放在最后一個(gè)位置产上，你從第一個(gè)開(kāi)始親，親到最后一個(gè)蛾狗。你需要嘗試1000次晋涣。但絕不會(huì)超過(guò)這個(gè)范圍。當(dāng)然實(shí)際情況也可能是O(1)沉桌，第一次成功了谢鹊。
我們通過(guò)這個(gè)算法得到了時(shí)間復(fù)雜度公式： O(n)
O(log n) 二分查找
接著上面的列子算吩。還記得召喚師峽谷里有個(gè)商店老爺爺嗎？他說(shuō)能為你打開(kāi)此次尋找的天機(jī)佃扼。將所有蠟像的序號(hào)都展示出來(lái)偎巢，并且他每次都能告訴你整個(gè)區(qū)間內(nèi)是否存在真正的老婆。你想了想那么我可以從中間對(duì)折拆分找呀兼耀，這樣可以每次直接排除掉一半艘狭。這個(gè)過(guò)程就像：
第一次詢(xún)問(wèn):** 500~1000** 他說(shuō)不存在， 1~499那么一定存在翠订。
第二次詢(xún)問(wèn):** 250~499** 他說(shuō)不存在巢音， 1~249那么一定存在。
第三次詢(xún)問(wèn):** 125~249** 他說(shuō)不存在尽超， 1~124那么一定存在官撼。
第四次詢(xún)問(wèn):** 63~124** 他說(shuō)不存在， 1~62那么一定存在似谁。
第五次詢(xún)問(wèn):** 31~62** 他說(shuō)不存在傲绣， 1~30那么一定存在。
第六次詢(xún)問(wèn):** 15~30** 他說(shuō)不存在巩踏， 1~15那么一定存在秃诵。
第七次詢(xún)問(wèn):** 7~14** 他說(shuō)不存在， 1~6那么一定存在塞琼。
第八次詢(xún)問(wèn):** 3~6** 他說(shuō)不存在菠净， 1~2那么一定存在。
第九次詢(xún)問(wèn):** 2** 他說(shuō)不對(duì)彪杉，那么結(jié)果只剩下1了毅往。
好，我們捋一捋派近。實(shí)際每次詢(xún)問(wèn)我們都可以排除一半絕對(duì)不可能存在的攀唯。也就是說(shuō)最多我們需要經(jīng)過(guò)9步即可完成從1000個(gè)老婆中出真正的老婆。
如果我們把它寫(xiě)成代碼就會(huì)是這個(gè)樣子：
//999個(gè)假老婆+一個(gè)真的
List<Wife> Wifes= {蠟像渴丸，蠟像侯嘀，蠟像...真老婆，蠟像}谱轨；
// 我自己
Lead myself =new Lead()戒幔；
int low=0; //最低位
int high = Wifes.length-1; //最高位
int mid; //折中猜想數(shù)
while( low<=high){
mid=(low+higt)/2
likeWife=Wifes.get(mid)；
if( kiss(likeWife)){
Log.i(“已找到老婆他在”+mid+“個(gè),趕緊抬回家碟嘴，遠(yuǎn)離召喚師峽谷”)溪食；
return ;
}
boolean deviation= elderlyHelp(likeWife)；
if(deviation){ //往左偏移 表示大了
high=mid-1娜扇；
}esle{ //往右偏移 表示小了
low=mid+1错沃；
}
}
}
//老爺爺?shù)膸椭?返回區(qū)間內(nèi)是否包含
boolean elderlyHelp(){
····
}
boolean kiss(Wife mWife){
//調(diào)用自己的么么噠方法 返回真假
return myself.kiss(mWife)；
}
這樣我們就推倒出二分法查找實(shí)際是是對(duì)數(shù)函數(shù)的反向冪運(yùn)算雀瓢。所以推倒出公式為：O(log n)
稍微說(shuō)一下log對(duì)數(shù)運(yùn)算枢析，也許你學(xué)過(guò)又忘了。log以10為底數(shù)多少次冪結(jié)果等于100刃麸，其實(shí)就是指多少個(gè)10相乘的結(jié)果為100醒叁。答案是兩個(gè)：10 × 10 = 100。所以log以10為底數(shù)的 2次冪等于100泊业。
O(n)對(duì)比 O(log n)
假定我們每一次myself.kiss用于激活的方法需要1秒鐘執(zhí)行把沼。當(dāng)采用第一種算法時(shí)，時(shí)間復(fù)雜度為O(n) 吁伺，那么需要1000秒才能找出老婆饮睬。但如果采用了二分查找，時(shí)間復(fù)雜度為 O(log n) 篮奄，那么僅需要9秒即可完成操作捆愁。其中n表示次數(shù)。那么由此可見(jiàn)O(log n) 比O(n)要快窟却。當(dāng)元素越多的時(shí)候昼丑，執(zhí)行的效率就尤其具有可比性。
題外話
好夸赫，那么到這里就講完了今天的內(nèi)容啦菩帝。如果你感興趣的話可以再去了解O(n!) n階乘的時(shí)間復(fù)雜度。當(dāng)n階越高茬腿，消耗的時(shí)間越長(zhǎng)胁附。這是計(jì)算機(jī)領(lǐng)域非常經(jīng)典的旅行商問(wèn)題。 感興趣戳這里過(guò)去繼續(xù)深入閱讀滓彰。
旅行推銷(xiāo)員問(wèn)題（英語(yǔ)：Travelling salesman problem, TSP）是這樣一個(gè)問(wèn)題：給定一系列城市和每對(duì)城市之間的距離控妻，求解訪問(wèn)每一座城市一次并回到起始城市的最短回路。它是組合優(yōu)化中的一個(gè)NP困難問(wèn)題揭绑，在運(yùn)籌學(xué)和理論計(jì)算機(jī)科學(xué)中非常重要弓候。
看完本篇并不能讓你成一個(gè)優(yōu)秀的工程獅，這是入門(mén)級(jí)別的基礎(chǔ)知識(shí)他匪。但如果因?yàn)槭悄憧赐赀@篇文章后產(chǎn)生了這種想法菇存，我的目的就達(dá)到了，至少已經(jīng)在通往優(yōu)秀工程獅的路上了邦蜜。那么更多的知識(shí)還需要長(zhǎng)久的打磨和學(xué)習(xí)依鸥。共勉 加油！
如何下次找到我?
- 關(guān)注我的簡(jiǎn)書(shū)
- 本篇同步Github倉(cāng)庫(kù):https://github.com/BolexLiu/MyNote (可以關(guān)注)
