為什么要學(xué)習(xí)復(fù)雜度分析涂佃？
我們用開發(fā)工具將代碼跑一遍，通過統(tǒng)計和監(jiān)控就能得到算法執(zhí)行的時間和占用的內(nèi)存蜈敢，為什么還要做算法的時間和空間復(fù)雜度分析辜荠？這種統(tǒng)計復(fù)雜度的方法我們稱為"事后統(tǒng)計法 ",這種統(tǒng)計方法有如下局限性：
- 測試結(jié)果依賴測試環(huán)境
- 測試結(jié)果受數(shù)據(jù)估摸影響很大
所以我們需要一個不需要具體數(shù)據(jù)和環(huán)境就能粗略估算算法執(zhí)行效率的方法。
大O復(fù)雜度表示法
復(fù)雜度分析包括：
- 時間復(fù)雜度分析
- 空間復(fù)雜度分析
時間復(fù)雜度
我們假設(shè)沒句代碼執(zhí)行的時間都是一個unit_time抓狭，因此所有代碼的執(zhí)行時間T(n)與每行代碼的執(zhí)行次數(shù)n成正比伯病，把這個規(guī)律總結(jié)成一個公式：
這就是大O時間復(fù)雜度表示法：
- T(n)表示代碼執(zhí)行的時間
- n表示數(shù)據(jù)規(guī)模的大小
- f(n)表示每行代碼執(zhí)行的次數(shù)總和
- O表示代碼的執(zhí)行時間T(n)與f(n)成正比
大O時間復(fù)雜度表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模的增長的變化趨勢，也叫漸進時間復(fù)雜度辐宾，簡稱時間復(fù)雜度狱从。當n很大時，比如1000000叠纹，公式中的低階季研、常量、系數(shù)并不左右增長的趨勢可以忽略誉察。例如T(n) = O(n+1)或T(n) = O(n2+2n+1)与涡，用大O表示法可以記為T(n) = O(n)、T(n) = O(n2)持偏。
時間復(fù)雜度分析
時間復(fù)雜度分析的技巧
只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
大O表示的是一種變化趨勢驼卖，所以我們只需要關(guān)注最大階的量級就可以了。例如一個函數(shù)鸿秆，有一個for循環(huán)執(zhí)行n次酌畜，其余代碼均只執(zhí)行一次，那么這個函數(shù)的時間復(fù)雜度就O(n)卿叽；一個函數(shù)有一個for循環(huán)執(zhí)行n次桥胞，還有一個for循環(huán)執(zhí)行n2次恳守，那這個函數(shù)的時間復(fù)雜度就是O(n2)。加法法則
兩個函數(shù)的時間復(fù)雜度相加贩虾，總的復(fù)雜度等于量級最大的那段代碼的復(fù)雜度催烘，原因同上一個技巧的解鎖。這里要注意一點缎罢，如果某個函數(shù)里面for循環(huán)循環(huán)執(zhí)行10000次伊群，而另一個函數(shù)循環(huán)執(zhí)行n次，那這兩個函數(shù)相加后總的復(fù)雜度為O(n)策精，因為大O表示的是一種變化趨勢舰始，只要是個確定的數(shù)，不論多么大都與n無關(guān)蛮寂，是常量階蔽午，這種當n趨于無限大時都可以忽略。乘法法則
嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積酬蹋，例如一個n次for循環(huán)嵌套另一個n次for循環(huán)及老，時間復(fù)雜度為O(n2)。
常見的復(fù)雜度量級
常量階O(1)
只要代碼不隨n的增大而增大范抓，時間復(fù)雜度就是O(1)對數(shù)階O(logn)
線性階O(n)
線性對數(shù)階O(nlogn)
k次方階O(n^k)
指數(shù)階O(2^n)
階乘階O(n!)
空間復(fù)雜度
空間復(fù)雜度表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系
空間復(fù)雜度的分析同時間復(fù)雜度骄恶。
最好、最壞情況時間復(fù)雜度
最好情況時間復(fù)雜度
在最理想的情況下匕垫，執(zhí)行一段代碼的時間復(fù)雜度最壞情況時間復(fù)雜度
在最糟糕的情況下僧鲁，執(zhí)行一段代碼的時間復(fù)雜度
平均情況時間復(fù)雜度
最好、最壞情況時間復(fù)雜度反映的是極端情況下的復(fù)雜度象泵，發(fā)生的概率不大寞秃。平均情況時間復(fù)雜度是將每種情況發(fā)生的概率考慮進去，將每種情況下的復(fù)雜度乘以發(fā)生這種情況的概率相加偶惠，這個值是概率論中的加權(quán)平均值春寿，也叫期望值。所以平均時間復(fù)雜度也稱加權(quán)平均時間復(fù)雜度或期望時間復(fù)雜度忽孽。
均攤時間復(fù)雜度
對一個數(shù)據(jù)結(jié)構(gòu)進行一組連續(xù)的操作绑改，大部分情況下時間復(fù)雜度都很低，只有個別情況下時間復(fù)雜度比較高兄一，且這些操作之間存在前后連貫的時序關(guān)系厘线，這種情況下，我們將這一組操作放在一起分析出革，看能否將時間復(fù)雜度較高的那次操作的耗時造壮，分攤到其他那些時間復(fù)雜度低的操作上，這就是攤還分析法骂束。通過攤還分析法得到的時間復(fù)雜度耳璧，我們稱為均攤時間復(fù)雜度硝全。一般均攤時間復(fù)雜度就等于最好時間復(fù)雜度。
如上圖楞抡，共n+1種情況，每種情況發(fā)生的概率都一樣析藕，前n種情況的時間復(fù)雜度為O(1),第n+1種情況的時間復(fù)雜度為O(n)召廷，那平均時間復(fù)雜度為O(1)。因此账胧，均攤時間復(fù)雜度就是一種特殊的平均時間復(fù)雜度竞慢。只是針對這種特殊場景，我們不需要再找出所有情況及發(fā)生的概率計算加權(quán)平均值治泥，能夠快速得到其時間復(fù)雜度筹煮。
以上內(nèi)容是對學(xué)習(xí)極客時間王爭出品的數(shù)據(jù)結(jié)構(gòu)與算法之美的總結(jié)，算法小白去訂閱學(xué)習(xí)吧居夹！
