前言
衡量一個(gè)算法的效率，可以從時(shí)間復(fù)雜度T(n) 和 空間復(fù)雜度S(n) 去分析。時(shí)間復(fù)雜度衡量算法執(zhí)行的時(shí)間惧蛹，空間復(fù)雜度衡量算法執(zhí)行消耗的內(nèi)存大小像云，默認(rèn)情況下都是分析最壞情況下的復(fù)雜度铐维。首先引入一個(gè)輔助函數(shù)f(n)，可理解為算法中代碼的執(zhí)行次數(shù)(也稱為頻度)害晦，如下面代碼：
代價(jià) 次數(shù)
for(int i = 0; i < n; i++){ c1 n
int j = i; c2 n-1
cout << j << endl; c3 n-1
}
此時(shí)f(n)=c1n + c2(n-1) + c3(n-1)枚抵。
時(shí)間復(fù)雜度
1.概念
對(duì)于時(shí)間復(fù)雜度來(lái)說(shuō)踱讨，代價(jià)即為當(dāng)前行代碼執(zhí)行時(shí)間榄审，當(dāng)n趨于無(wú)窮大的時(shí)候莱革，記T(n)=O(f(n))驮吱，被稱為算法的漸進(jìn)時(shí)間復(fù)雜度，又簡(jiǎn)稱為時(shí)間復(fù)雜度，大O給出的是函數(shù)f(n)唯一的的漸進(jìn)上界琼腔。因?yàn)閚趨于無(wú)窮大洲赵，所以f(n)的常數(shù)項(xiàng)變化對(duì)整體影響不大辅鲸，直接去掉。所以對(duì)于上述代碼管行，T(n)=O(n)。
2.常見(jiàn)時(shí)間復(fù)雜度
- 常數(shù)階
T(n)=O(1)
int i = 0;
- 線性階
T(n) = O(n)
for(int i = 0; i < n; i++);
- 平方階
T(n)=O(n2)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
- 對(duì)數(shù)階
T(n)=O(logn)
int i = 2;
while(i < n) i *= 2;
這里說(shuō)一下邪媳，設(shè)循環(huán)次數(shù)為t捐顷，2^t < n ==> t < logn。
3.求解含遞歸算法的時(shí)間復(fù)雜度
包含遞歸的算法很常見(jiàn)雨效，比如熟悉的斐波那契數(shù)列：
int func(int n) {
if (n <= 1) return 1;
else return func(n - 1) + func(n - 2);
}
對(duì)于這種算法迅涮，上面介紹的常用時(shí)間復(fù)雜度有些力不從心。所以針對(duì)這種算法徽龟，我們直接將復(fù)雜度表示為T(n)=T(n-1)+T(n-2)+1叮姑，+1是指else中問(wèn)題分解與解合并的代價(jià)。那問(wèn)題是怎么去計(jì)算它出T(n)呢据悔？這里介紹兩種方法代入法和主方法传透。
代入法：首先猜測(cè)解的形式，然后通過(guò)歸納法求出解中的常數(shù)屠尊，并證明解是正確的旷祸。
對(duì)于斐波那契數(shù)列算法，我們猜測(cè)其解為T(n)=O(n^2)讼昆，那代入法要求證明托享，存在常數(shù)c>0骚烧，有T(n)<=cn^2，先假設(shè)此上界對(duì)于所有m<n都成立闰围，然后代入遞歸式：
T(n) <= c(n-1)^2+c(n-2)^2+1
<= 2cn^2-6cn
<= cn^2赃绊。
其中對(duì)于c>=1，最后一步都成立羡榴。接著數(shù)學(xué)歸納法要求證明解在邊界條件下也成立碧查，如果成立，則猜想正確校仑。
當(dāng)n=1時(shí)忠售，T(1)=1<=c;
因此，對(duì)于所有c>=1迄沫，都有T(n)<=cn^2稻扬，猜想成立。代入法的成功很大程度上看你猜測(cè)的解是否正確羊瘩，很靠經(jīng)驗(yàn)泰佳，偶爾還需要?jiǎng)?chuàng)造力。雖然如此尘吗，但在實(shí)際的分析中逝她，它也是一個(gè)不錯(cuò)的方法。
主方法：主方法為形如T(n)=aT(n/b)+f(n)的遞歸式提供了一種"菜譜式"的求解方法睬捶。其中a>=1,b>1且為常數(shù)黔宛，f(n)是一個(gè)漸進(jìn)正函數(shù)（即n趨近無(wú)窮時(shí)，f(n)是一個(gè)正數(shù)）擒贸，n為非負(fù)整數(shù)宁昭。該遞歸式的含義是，將規(guī)模為n的問(wèn)題分解成了a個(gè)子問(wèn)題酗宋，每個(gè)子問(wèn)題規(guī)模為n/b，而f(n)表示問(wèn)題分解和和子問(wèn)題解合并的代價(jià)疆拘。 主方法通過(guò)下面定理得到T(n)：
（1）若存在某個(gè)常數(shù)k>0蜕猫，有
f(n)=O(n^logb(a-k))，則T(n)=Θ(n^logb(a))哎迄。
（2）若f(n)=Θ(n^logb(a))回右，則T(n)=Θ(n^logb(a)*lgn)。
（3）若存在某個(gè)常數(shù)k>0漱挚，有f(n)=Ω(n^logb(a+k))翔烁，且存在常數(shù)c<1和所有足夠大的n有af(n/b)<=cf(n)，則T(n)=Θ(f(n))旨涝。
O表示小于等于（即上界）蹬屹，Θ表示等于，Ω表示大于等于（即下界），因此對(duì)上述定理歸納后可得：
（1）若
f(n)<=n^logb(a)慨默，則T(n)=Θ(n^logb(a))贩耐。
（2）若f(n)==n^logb(a))，則T(n)=Θ(n^logb(a)*lgn)厦取。
（3）若f(n)>=n^logb(a)潮太，且存在常數(shù)c<1和所有足夠大的n有af(n/b)<=cf(n)，則T(n)=Θ(f(n))虾攻。
主方法使用：
情況1：
T(n) = 9T(n/3) + n
a=9铡买，b=3，nlogb(a)=n2霎箍，因?yàn)?code>f(n)=n <= n^2奇钞，所以用定理1，得T(n)=Θ(n^2)朋沮。
情況2：
T(n) = T(2n/3) + 1
a=1蛇券，b=3/2，n^logb(a)=1樊拓，因?yàn)?code>f(n)=1 == 1纠亚，所以用定理2，得T(n)=Θ(lgn)筋夏。
情況3：
T(n) = 3T(n/4) + nlgn
a=3蒂胞，b=4，nlogb(a)=nlog4(3)<=n^0.793条篷，因?yàn)?code>f(n)=nlgn >= n^0.793骗随，再當(dāng)n足夠大時(shí)，對(duì)于c=3/4赴叹，有af(n/b)<=cf(n)鸿染，所以用定理3，得T(n)=Θ(nlgn)乞巧。
4.常用時(shí)間復(fù)雜度比較
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2?) < O(n!)
5.小結(jié)
觀察算法中有幾重for循環(huán)涨椒，只有一重則時(shí)間復(fù)雜度為n，二重則為n^2绽媒，依此類推蚕冬，如果有二分則為logn，如果一個(gè)for循環(huán)套一個(gè)二分是辕，那么時(shí)間復(fù)雜度則為nlogn囤热，如果算法含有遞歸，則根據(jù)上面兩種方法進(jìn)行推導(dǎo)获三。
結(jié)尾
1.平均情況時(shí)間復(fù)雜度：
（1）上面討論的都是最壞情況下得時(shí)間復(fù)雜度旁蔼，而一般最好锨苏、最壞時(shí)間復(fù)雜度是在極端條件下出現(xiàn)的，發(fā)生的概率不大牌芋，不能代表平均水平蚓炬。所以為了更好的表示算法復(fù)雜度，就引入平均時(shí)間復(fù)雜度躺屁。
（2）平均情況時(shí)間復(fù)雜度通過(guò)代碼在所有可能情況下執(zhí)行次數(shù)的加權(quán)平均值表示肯夏。雖然平均情況時(shí)間復(fù)雜度可以很好的反應(yīng)算法的效率，但在實(shí)際應(yīng)用中犀暑，平均運(yùn)行時(shí)間很難通過(guò)分析得到驯击，一般都是通過(guò)運(yùn)行一定數(shù)量的實(shí)驗(yàn)數(shù)據(jù)后估算出來(lái)的。所以一般在沒(méi)有特殊說(shuō)明的情況下耐亏，時(shí)間復(fù)雜度都是指最壞時(shí)間復(fù)雜度徊都。
2.空間復(fù)雜度：
空間復(fù)雜度S(n)表示一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間得大小，它包括广辰，為參數(shù)表中形參變量分配的存儲(chǔ)空間和為函數(shù)體中定義的局部變量分配的存儲(chǔ)空間兩個(gè)部分暇矫。
3.最后說(shuō)一句：
實(shí)際應(yīng)用中，時(shí)間復(fù)雜度和空間復(fù)雜度需要合理的配合择吊，如常用的通過(guò)犧牲空間復(fù)雜度來(lái)減小時(shí)間復(fù)雜度李根。
【關(guān)注公眾號(hào)DoCode，每日一道LeetCode几睛，將零碎時(shí)間利用起來(lái)】
