復雜度分析（上）：如何分析、統(tǒng)計算法的執(zhí)行效率和資源消耗阿蝶？
-
把代碼跑一遍雳锋，通過統(tǒng)計、監(jiān)控得到算法執(zhí)行時間和占用內(nèi)存大小的方法叫作事后統(tǒng)計法羡洁。事后統(tǒng)計法的局限性：
- 測試結(jié)果非常依賴測試環(huán)境
- 測試結(jié)果受數(shù)據(jù)規(guī)模的影響很大
時間玷过、空間復雜度分析法，不用具體測試數(shù)據(jù)來測試筑煮，就可以粗略地估計算法的執(zhí)行效率辛蚊。
大 O 時間復雜度表示法
大 O 時間復雜度表示法：所有代碼的執(zhí)行時間 T(n) 與每行代碼的執(zhí)行次數(shù) n 成正比。
T(n)：代碼執(zhí)行時間 n：數(shù)據(jù)規(guī)模大小 f(n)：每行代碼執(zhí)行的次數(shù)總和 O：表示 T(n) 與 f(n) 成正比
大 O 時間復雜度表示法實際上并不具體表示代碼真正的執(zhí)行時間真仲，而是表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢袋马，所以也叫做漸進時間復雜度，簡稱時間復雜度秸应。
時間復雜度分析
- 只關注循環(huán)執(zhí)行次數(shù)最多的一段代碼
- 加法法則：總復雜度等于量級最大的那段代碼的復雜度
- 乘法法則：嵌套代碼的復雜度等于嵌套內(nèi)外代碼復雜度的乘積
幾種常見時間復雜度實例分析
以上復雜度量級可以粗略地分為兩類虑凛，多項式量級和非多項式量級。
其中软啼，非多項式量級只有：
桑谍，當數(shù)據(jù)規(guī)模 n 越來越大時，非多項式量級算法的執(zhí)行時間會急劇增加焰宣，求解問題的執(zhí)行時間會無限增長霉囚。所以捕仔，非多項式時間復雜度的算法其實是非常低效的算法匕积。
-
多項式時間復雜度
- O(1)：一般情況下，只要算法中不存在循環(huán)語句榜跌、遞歸語句闪唆，即使有成千上萬行的代碼，其時間復雜度也是Ο(1)钓葫。
- O(logn)悄蕾、O(nlogn)：不管是以 2 為底、以 3 為底，還是以 10 為底帆调，因為對數(shù)可以相互轉(zhuǎn)化奠骄，同時又要忽略常數(shù)约谈，我們可以把所有對數(shù)階的時間復雜度都記為 O(logn)曹傀。
- O(m+n)、O(m*n)：無法事先評估 m 和 n 誰的量級大來決定省略哪個延曙，所以代碼的復雜度由兩個數(shù)據(jù)的規(guī)模來決定芹务。
空間復雜度分析
空間復雜度分析全稱就是漸進空間復雜度（asymptotic space complexity）蝉绷，表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關系。
空間復雜度是指算法在計算機內(nèi)執(zhí)行時所需存儲空間的度量枣抱。一般所討論的是除正常占用內(nèi)存開銷后額外的內(nèi)存消耗規(guī)模熔吗。
常見的空間復雜度就是 $ O(1)、O(n)佳晶、O(n^2 )桅狠，像O(logn)、O(nlogn) 這樣的對數(shù)階復雜度平時都用不到宵晚。
小結(jié)：
復雜度也叫漸進復雜度垂攘，包括時間復雜度和空間復雜度，用來分析算法執(zhí)行效率與數(shù)據(jù)規(guī)模之間的增長關系淤刃，可以粗略地表示晒他，越高階復雜度的算法，執(zhí)行效率越低逸贾。常見的復雜度并不多陨仅，從低階到高階有：
