復(fù)雜度分析是整個算法學(xué)習(xí)的精髓姨俩，只要掌握它，數(shù)據(jù)結(jié)構(gòu)和算法的內(nèi)容基本就掌握了一半师郑。
大O復(fù)雜度表示法
大O時間復(fù)雜度實際上并不具體表示代碼真正的執(zhí)行時間环葵，而是表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢，簡稱時間復(fù)雜度宝冕。
1张遭、只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
只要關(guān)注for循環(huán)執(zhí)行次數(shù)就可以了，執(zhí)行n次地梨，所以總時間復(fù)雜度就是O(n)菊卷。
2、加法法則：總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度
以上代碼有三個for循環(huán)宝剖，sum1循環(huán)中循環(huán)次數(shù)是100洁闰，跟n無關(guān)，復(fù)雜度為O(1)万细，sum2循環(huán)中循環(huán)次數(shù)為n扑眉，復(fù)雜度為O(n)，sum3循環(huán)是雙重循環(huán)赖钞，復(fù)雜度為O(n2)腰素。最終復(fù)雜度就等于量級最大的那段，也就是O(n2)雪营。
3弓千、乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積。
以上代碼有兩個方法是卓缰，每個方法都有一個for循環(huán)计呈，復(fù)雜度都為O(n)，cal3()方法中調(diào)用了f()方法征唬，
根據(jù)乘法法則捌显，最終復(fù)雜度為O(n2)。
4总寒、常見時間復(fù)雜度O(logn)扶歪、O(nlogn)
以上代碼中，變量i是等比增長的，復(fù)雜度就是O(logn)善镰。
空間復(fù)雜度分析
表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系妹萨，稱為空間復(fù)雜度。
以上代碼炫欺，數(shù)組a申請了一個大小為n的存儲空間乎完，空間復(fù)雜度就是O(n)。
最好品洛、最壞情況時間復(fù)雜度树姨、平均情況時間復(fù)雜度
閱讀以上代碼，不同情況下桥状，時間復(fù)雜度是不一樣的帽揪。為了表示代碼在不同情況下的時間復(fù)雜度，我們引入三個概念：最好情況時間復(fù)雜度辅斟、最壞情況時間復(fù)雜度和平均情況時間復(fù)雜度转晰。
以上代碼中，最好情況時間復(fù)雜度是O(1)士飒，最壞情況時間復(fù)雜度是O(n)查邢，平均情況時間復(fù)雜度需要引入概率，假設(shè)要尋找的元素在數(shù)組中與不在數(shù)組中各占1/2酵幕，數(shù)組中n個數(shù)據(jù)侠坎，出現(xiàn)在每個位置的概率為1/n，所以根據(jù)概率乘法原則裙盾，出現(xiàn)在數(shù)組中每個位置的概率為1/2n。那么平均時間復(fù)雜度的計算過程為：1*1/2n+2*1/2n+3*1/2n+……+n*1/2n+n*1/2 = （3n+1）/ 4 他嫡，這個就是加權(quán)平均值番官。平均時間復(fù)雜度是O(n)。
均攤時間復(fù)雜度
以上代碼钢属，最好情況復(fù)雜度為O(1)徘熔，數(shù)組有空間直接插入數(shù)據(jù)。最壞情況時間復(fù)雜度為O(n)淆党，恰巧數(shù)組沒有空間需要循環(huán)遍歷一次酷师。平均時間復(fù)雜度為O(1)，數(shù)組長度為n染乌，外加如果越界的一次山孔，概率都是1/(n+1)，加權(quán)平均的計算過程：1*1/(n+1)+1*1/(n+1)+……+1*1/(n+1)+n*1/(n+1) =?O(1)荷憋。
我們再來分析這個例子台颠，復(fù)雜度為O(1)的情況執(zhí)行n-1次，才會出現(xiàn)一次O(n)勒庄，出現(xiàn)的頻率是很有規(guī)律的串前。所以針對這樣的特殊場景瘫里，我們引入均攤時間復(fù)雜度，大致思路就是將耗時最多的那一次O(n)荡碾，均攤到n-1次O(1)上谨读，均攤結(jié)果就是O(1)。
