復(fù)雜度分析
在學(xué)習(xí)算法之前首先要明確一個(gè)衡量算法優(yōu)劣的概念拨与，算法的復(fù)雜度。
- 時(shí)間維度：是指執(zhí)行當(dāng)前算法所消耗的時(shí)間艾猜，通常用
時(shí)間復(fù)雜度來(lái)描述买喧；- 空間維度：是指執(zhí)行當(dāng)前算法所需要占用的內(nèi)存空間，通常用
空間復(fù)雜度來(lái)描述匆赃。
時(shí)間復(fù)雜度計(jì)算---算法的漸進(jìn)時(shí)間復(fù)雜度： T(n) = O(f(n))
舉個(gè)例子：
for (int i=0; i<n; i++) { a++; b++; }對(duì)于這個(gè)例子淤毛，假設(shè)每行代碼執(zhí)行的時(shí)間都是
1單位時(shí)間，那么第一行消耗1單位算柳，第二行和第三行每次消耗1單位低淡，循環(huán)n次，那么就總共消耗n+n單位時(shí)間瞬项，所以該例子中蔗蹋，總的時(shí)間為：T(n) = (1+2n) 單位時(shí)間可以看出，該算法的耗時(shí)是隨著n變化而變化的囱淋，與其他變量無(wú)關(guān)猪杭，就可以將該算法的時(shí)間復(fù)雜度表示為
O(n)。
注意：這里的時(shí)間復(fù)雜度并不等價(jià)于表示算法的執(zhí)行時(shí)間妥衣，只是用來(lái)表示代碼執(zhí)行時(shí)間的增長(zhǎng)變化趨勢(shì)皂吮。在實(shí)際情況中一般關(guān)注算法的最壞運(yùn)行情況戒傻。
常見(jiàn)的時(shí)間復(fù)雜度量級(jí)：
- 常數(shù)階
O(1)
- 算法內(nèi)沒(méi)有循環(huán)等復(fù)雜結(jié)構(gòu)。
- 線性階
O(n)
- 單層循環(huán)蜂筹，代碼執(zhí)行n遍需纳。
- 對(duì)數(shù)階
O(logN)
- 在循環(huán)中，循環(huán)結(jié)束條件以乘法的形式遞增艺挪，例如
while(i<n) i=i*2不翩，i距離n是越來(lái)越近的，設(shè)循環(huán)x次后退出闺属，那么2的x次方=n,x=log2n慌盯，所以復(fù)雜度簡(jiǎn)化為：O(logN)- 線性對(duì)數(shù)階
O(nlogN)
- 將時(shí)間復(fù)雜度為O(logN)的算法循環(huán)n次。即有兩層循環(huán)掂器。
- 平方階
O(n2)
- 循環(huán)嵌套亚皂，都是O(n)，從這可以推出O(n^k)
他們的大小關(guān)系：
O(1)常數(shù)階 < O(logn)對(duì)數(shù)階 < O(n)線性階 < O(n2)平方階 < O(n3)(立方階) < O(2n) (指數(shù)階)
空間復(fù)雜度：類似時(shí)間復(fù)雜度国瓮，不是具體計(jì)算程序?qū)嶋H占用空間灭必，是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)大小的一個(gè)度量，常見(jiàn)的有S(n) = O(1), O(n), O(n2)
- O(1)表示臨時(shí)空間不隨著某個(gè)變量n的變化而變化乃摹。
- O(n)禁漓，分配了n個(gè)大小的存儲(chǔ)空間
