程序猿可以讓步瘾境，卻不可以退縮，可以羞澀陪每，卻不可以軟弱影晓，總之，程序員必須是勇敢的檩禾。
時(shí)間復(fù)雜度序言
當(dāng)前兩天我寫(xiě)完<<大話數(shù)據(jù)結(jié)構(gòu)>>的序言的時(shí)候,我就在想,我該如何把從大話數(shù)據(jù)結(jié)構(gòu)中對(duì)應(yīng)用開(kāi)發(fā)人員有用的知識(shí)提煉出來(lái)?我是該如同課本一樣把所有的知識(shí)羅列個(gè)遍?還是如何如何,我想如果我把所有的東西都羅列出來(lái),那還不如讓廣大的讀者去自己看這本書(shū)呢,畢竟我這小渣渣的層次面還跟不上程杰大神呢,幽默度更不用說(shuō)了,所以我想了幾天 決定把對(duì)開(kāi)發(fā)人員有用的整理出來(lái),其實(shí)也是為了自己以后能夠快速地找到我想要的知識(shí)點(diǎn).利人利己的事情,何樂(lè)而不為呢?
時(shí)間復(fù)雜度的概念以及實(shí)際作用
計(jì)算機(jī)科學(xué)中挂签，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間盼产。這是一個(gè)關(guān)于代表算法輸入值的字符串的長(zhǎng)度的函數(shù)饵婆。時(shí)間復(fù)雜度常用大O符號(hào)表述，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)戏售。使用這種方式時(shí)侨核，時(shí)間復(fù)雜度可被稱(chēng)為是漸近的，它考察當(dāng)輸入值大小趨近無(wú)窮時(shí)的情況灌灾。
說(shuō)白了,就是對(duì)函數(shù)或者方法的復(fù)雜程度的度量.那么我們什么時(shí)候使用這個(gè)時(shí)間復(fù)雜度呢?在實(shí)際中,我們或多或少都要寫(xiě)一些方法或者函數(shù),但是如果函數(shù)的時(shí)間復(fù)雜度過(guò)大,就會(huì)影響到整個(gè)項(xiàng)目或者工程的運(yùn)行,耗損不必要的內(nèi)存空間,影響用戶的體驗(yàn)效果,一旦用戶的體驗(yàn)效果不好,那么就是老一套了,該需求,改需求再改需求...但是我們需要改動(dòng)那一些函數(shù)或者方法呢?這就需要到我們的"時(shí)間復(fù)雜度"相關(guān)的知識(shí)了.(當(dāng)然了,空間復(fù)雜度也是需要的,但是我還沒(méi)看到那,所以,見(jiàn)諒~)
算法時(shí)間復(fù)雜度的定義
定義:在進(jìn)行算法分析時(shí)候,語(yǔ)句總的執(zhí)行次數(shù)T(n)是關(guān)于問(wèn)題規(guī)模n的函數(shù),進(jìn)而分型T(n)隨著n的變化情況并確定T(n)的數(shù)量級(jí).算法的時(shí)間復(fù)雜度,也就是算法的時(shí)間度量記作:T(n)=O(f(n)).它表示隨著問(wèn)題規(guī)模n的增大,算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同,稱(chēng)作算法的漸近時(shí)間復(fù)雜度,簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度.其中f(n)是問(wèn)題規(guī)模n的某個(gè)函數(shù).
這里用大寫(xiě)的O( )來(lái)體現(xiàn)算法時(shí)間復(fù)雜度的記法,我們稱(chēng)之為大O記法.
分析一個(gè)函數(shù)或者算法的時(shí)間復(fù)雜度
分析一個(gè)函數(shù)或者算法的時(shí)間復(fù)雜度,其實(shí)就是 推導(dǎo)大O階
推導(dǎo)大O階:
1.用常熟1取代運(yùn)行時(shí)間中的所有加法常數(shù).
2.在修改后的運(yùn)行次數(shù)函數(shù)中,只保留最高階項(xiàng).
3.如果最高階項(xiàng)存在且不是1,則去除與這個(gè)像相乘的常數(shù).
得到的結(jié)果就是大O階.
正如書(shū)中所講的一樣,這就是游戲攻略,我們拿著這個(gè)游戲攻略開(kāi)始戰(zhàn)斗吧.
比較常見(jiàn)的大O階分析
- 常數(shù)階
我們來(lái)看下面的這個(gè)算法,作為程序員的我們可能看一眼就知道它是一個(gè)順序結(jié)構(gòu),并且執(zhí)行了三次.那么它的時(shí)間復(fù)雜度是不是就是常數(shù)3呢?因?yàn)閳?zhí)行了三次呀,這可是大錯(cuò)特錯(cuò)了.
我們來(lái)看推導(dǎo)大O階的方法,首先運(yùn)行次數(shù)是3,我們根據(jù)游戲攻略的第一步,就是要把常數(shù)項(xiàng)3改成1,再根據(jù)第二步和第三步,保留最高項(xiàng),發(fā)現(xiàn)根本沒(méi)有最高項(xiàng),所以這個(gè)算法的時(shí)間復(fù)雜度為O(1).當(dāng)然了,只有順序結(jié)構(gòu)的時(shí)候,不管你執(zhí)行多少次,時(shí)間復(fù)雜度統(tǒng)統(tǒng)是O(1),也就是常數(shù)階.當(dāng)然了,分支結(jié)構(gòu)也是一樣的不管條件是真或者假,你都會(huì)發(fā)現(xiàn)整個(gè)分支結(jié)構(gòu)只是執(zhí)行了一次,所以,跟順序結(jié)構(gòu)大同小異,時(shí)間復(fù)雜度也是O(1).
- 常數(shù)階
順序結(jié)構(gòu)
//順序結(jié)構(gòu)
int sum =0, n= 100;//執(zhí)行一次
sum = (1+n)/2;//執(zhí)行一次
NSLog(@"%d",sum);//執(zhí)行一次
分支結(jié)構(gòu)
//分支結(jié)構(gòu)
//整個(gè)分支結(jié)構(gòu)不管條件如何都只執(zhí)行一次
if (/* DISABLES CODE */ (1) != 2) {
NSLog(@"1真的不等于2幺~");//執(zhí)行一次
}else{
NSLog(@"1等于2");//執(zhí)行一次
}
- 線性階
下面這是一個(gè)for循環(huán),那么它的時(shí)間復(fù)雜度又是多少呢?首先循環(huán)體就是一個(gè)執(zhí)行一次的循環(huán)體,總共執(zhí)行了n次,那么執(zhí)行次數(shù)就是f(n) =n,啟動(dòng)我們的游戲攻略三部曲知道,時(shí)間復(fù)雜度就是為O(n).具體的步驟就不詳細(xì)說(shuō)了,因?yàn)樘?jiǎn)單了不是?
- 線性階
for循環(huán)結(jié)構(gòu)
for (int i = 0; i< n; i++) {
NSLog(@"執(zhí)行一次");//執(zhí)行一次
}
- 3.對(duì)數(shù)階
來(lái)來(lái)來(lái),接著看這個(gè)while循環(huán)結(jié)構(gòu),我們不難發(fā)現(xiàn),當(dāng)count大于n的時(shí)候,循環(huán)體就會(huì)結(jié)束,循環(huán)體中count不斷的乘以2,那么執(zhí)行次數(shù)是多少呢? 2^x = n 可得到 x = log2n;所以根據(jù)游戲攻略我們可以知道這個(gè)while循環(huán)體的時(shí)間復(fù)雜度是 O(log n);感覺(jué)自己看到這都能困了,嘿嘿,懵了,這里要著重看一下.
while循環(huán)結(jié)構(gòu)
int count = 1;
while (count < n) {
count = count * 2;//執(zhí)行一次
}
- 4.平方階
實(shí)際應(yīng)用中肯定不能像上面那么只有單個(gè)結(jié)構(gòu),可能有兩種或者兩種以上的結(jié)構(gòu),下面看一下兩個(gè)for循環(huán)嵌套的時(shí)間復(fù)雜度又是如何呢? 我們先看一個(gè)特殊的嵌套,下面的這個(gè)嵌套是兩層都進(jìn)行n次循環(huán),那么總的執(zhí)行次數(shù)函數(shù)就是 f(n) = n^2;接著再根據(jù)我們的游戲攻略一頓計(jì)算,知道我們的時(shí)間復(fù)雜度是 O(n^2 );
兩層都執(zhí)行n次的for循環(huán)
for (int i = 0; i< n; i++) {
for (int j = 0; j< n; i++) {
NSLog(@"這個(gè)地方是時(shí)間復(fù)雜度為O(1)的算法");
}
}
如果是下面的這種呢?外層循環(huán)n次,內(nèi)層循環(huán)m次,我們又該如何求解復(fù)雜度呢?其實(shí)跟上面是大同小異的,我們只需要把上面的其中一個(gè)n換成m就好了,所以時(shí)間復(fù)雜度為O(m*n );
for (int i = 0; i< n; i++) {
for (int j = 0; j< m; i++) {
NSLog(@"這個(gè)地方是時(shí)間復(fù)雜度為O(1)的算法");
}
}
那么,再看一下下面的這個(gè)嵌套,我們分析一下它總共執(zhí)行幾次,由于當(dāng)i = 0時(shí),內(nèi)循環(huán)執(zhí)行n此,當(dāng)n = 1時(shí), 執(zhí)行了 n - 1 次, ...當(dāng) i = n-1 時(shí), 執(zhí)行了1次,所以總的執(zhí)行次數(shù)為:
</b>
n + (n -1) +( n -2 ) +.... +1 = n(n +1)/2 = n^2/2 + n/2
根據(jù)我們的游戲秘籍的三部曲,我們可以分析出來(lái),時(shí)間復(fù)雜度為 O( n^2 );
for (int i = 0; i< n; i++) {
for (int j = i; j< n; j++) {
NSLog(@"這個(gè)地方是時(shí)間復(fù)雜度為O(1)的算法");
}
}
- 5.函數(shù)的調(diào)用
我們看一下 如何我們調(diào)用函數(shù)或者方法,那么該如何計(jì)算時(shí)間復(fù)雜度呢?這里我調(diào)用OC中的方法,然后就是下面的這個(gè),其實(shí)我們只要用嵌套的眼光看待就行,根據(jù)我們的游戲秘籍 不難得到下面的這個(gè)時(shí)間復(fù)雜度是 O (n ^2);如果函數(shù)或者方法中有其他的按照嵌套的規(guī)律來(lái)計(jì)算時(shí)間復(fù)雜度就好;額
for (int i = 0; i< n; i++) {
for (int j = 0; j< n; j++) {
[self function];
}
}
-(void)function{
NSLog(@"這個(gè)地方是時(shí)間復(fù)雜度為O(1)的算法");
}
常見(jiàn)的時(shí)間復(fù)雜度
我就直接上圖了,主要是比較集中常見(jiàn)的時(shí)間復(fù)雜度的大小.
時(shí)間復(fù)雜度總結(jié) :時(shí)間復(fù)雜度對(duì)我們開(kāi)發(fā)過(guò)程中做算法以及項(xiàng)目的優(yōu)化有著極大的幫助.雖然我們作為的是一個(gè)開(kāi)發(fā)人員,不是一個(gè)科研人員,但是,我們了解時(shí)間復(fù)雜度的概念和作用是有著很大的優(yōu)勢(shì)的,時(shí)間復(fù)雜度主要就是掌握游戲攻略三部曲就好了.文筆不好如果有什么問(wèn)題或者意見(jiàn),歡迎評(píng)論.謝謝.
