一、什么是復(fù)雜度分析派撕？
1.數(shù)據(jù)結(jié)構(gòu)和算法解決是“如何讓計算機更快時間废麻、更省空間的解決問題”。
2.因此需從執(zhí)行時間和占用空間兩個維度來評估數(shù)據(jù)結(jié)構(gòu)和算法的性能列林。
3.分別用時間復(fù)雜度和空間復(fù)雜度兩個概念來描述性能問題瑞你，二者統(tǒng)稱為復(fù)雜度。
4.復(fù)雜度描述的是算法執(zhí)行時間（或占用空間）與數(shù)據(jù)規(guī)模的增長關(guān)系希痴。
二者甲、為什么要進行復(fù)雜度分析？
1.和性能測試相比润梯，復(fù)雜度分析有不依賴執(zhí)行環(huán)境过牙、成本低、效率高纺铭、易操作寇钉、指導(dǎo)性強的特點。
2.掌握復(fù)雜度分析舶赔，將能編寫出性能更優(yōu)的代碼扫倡，有利于降低系統(tǒng)開發(fā)和維護成本。
三、如何進行復(fù)雜度分析撵溃？
1.大O表示法
1）來源
算法的執(zhí)行時間與每行代碼的執(zhí)行次數(shù)成正比疚鲤，用T(n) = O(f(n))表示，其中T(n)表示算法執(zhí)行總時間缘挑，f(n)表示每行代碼執(zhí)行總次數(shù)集歇，而n往往表示數(shù)據(jù)的規(guī)模。
2）特點
以時間復(fù)雜度為例语淘，由于時間復(fù)雜度描述的是算法執(zhí)行時間與數(shù)據(jù)規(guī)模的增長變化趨勢诲宇，所以常量階、低階以及系數(shù)實際上對這種增長趨勢不產(chǎn)決定性影響惶翻，所以在做時間復(fù)雜度分析時忽略這些項姑蓝。
2.復(fù)雜度分析法則
1）單段代碼看高頻：比如循環(huán)。
2）多段代碼取最大：比如一段代碼中有單循環(huán)和多重循環(huán)吕粗，那么取多重循環(huán)的復(fù)雜度纺荧。
3）嵌套代碼求乘積：比如遞歸、多重循環(huán)等
4）多個規(guī)模求加法：比如方法有兩個參數(shù)控制兩個循環(huán)的次數(shù)颅筋，那么這時就取二者復(fù)雜度相加宙暇。
四、常用的復(fù)雜度級別议泵？
多項式階：隨著數(shù)據(jù)規(guī)模的增長客给，算法的執(zhí)行時間和空間占用，按照多項式的比例增長肢簿。包括靶剑，
O(1)（常數(shù)階）、O(logn)（對數(shù)階）池充、O(n)（線性階）桩引、O(nlogn)（線性對數(shù)階）、O(n2)（平方階）收夸、O(n3)（立方階）
非多項式階：隨著數(shù)據(jù)規(guī)模的增長坑匠，算法的執(zhí)行時間和空間占用暴增，這類算法性能極差卧惜。包括厘灼，
O(2^n)（指數(shù)階）、O(n!)（階乘階）
五咽瓷、復(fù)雜度分析的4個概念
1.最壞情況時間復(fù)雜度：代碼在最理想情況下執(zhí)行的時間復(fù)雜度设凹。
2.最好情況時間復(fù)雜度：代碼在最壞情況下執(zhí)行的時間復(fù)雜度。
3.平均時間復(fù)雜度：用代碼在所有情況下執(zhí)行的次數(shù)的加權(quán)平均值表示茅姜。
4.均攤時間復(fù)雜度：在代碼執(zhí)行的所有復(fù)雜度情況中絕大部分是低級別的復(fù)雜度闪朱，個別情況是高級別復(fù)雜度且發(fā)生具有時序關(guān)系時，可以將個別高級別復(fù)雜度均攤到低級別復(fù)雜度上》茏耍基本上均攤結(jié)果就等于低級別復(fù)雜度锄开。
六、為什么要引入這4個概念称诗？
1.同一段代碼在不同情況下時間復(fù)雜度會出現(xiàn)量級差異萍悴，為了更全面，更準確的描述代碼的時間復(fù)雜度寓免，所以引入這4個概念退腥。
2.代碼復(fù)雜度在不同情況下出現(xiàn)量級差別時才需要區(qū)別這四種復(fù)雜度。大多數(shù)情況下再榄，是不需要區(qū)別分析它們的。
七享潜、如何分析平均困鸥、均攤時間復(fù)雜度？
1.平均時間復(fù)雜度
代碼在不同情況下復(fù)雜度出現(xiàn)量級差別剑按，則用代碼所有可能情況下執(zhí)行次數(shù)的加權(quán)平均值表示疾就。
2.均攤時間復(fù)雜度
兩個條件滿足時使用：
1）代碼在絕大多數(shù)情況下是低級別復(fù)雜度，只有極少數(shù)情況是高級別復(fù)雜度艺蝴；
2）低級別和高級別復(fù)雜度出現(xiàn)具有時序規(guī)律猬腰。均攤結(jié)果一般都等于低級別復(fù)雜度。
