復(fù)雜度分析
? ??數(shù)據(jù)結(jié)構(gòu)和算法本身解決的是 代碼執(zhí)行速度快 和 節(jié)省占用的內(nèi)存 的問題，那么如何衡量你寫的算法的執(zhí)行效率呢？這里我們就要用到 復(fù)雜度分析：時(shí)間 和 空間 復(fù)雜度分析。
? ? 復(fù)雜度分析 是整個(gè)算法學(xué)習(xí)的精髓，是我們必須要掌握的，只要掌握了它，數(shù)據(jù)結(jié)構(gòu)和算法的內(nèi)容基本上就掌握了一半。
為什么需要復(fù)雜度分析
? ?我們能夠通過統(tǒng)計(jì)、監(jiān)控，就能得到算法執(zhí)行的時(shí)間和占用的內(nèi)存大小， 那么我們?為什么?需要做 復(fù)雜度分析。首先這前面這種通過統(tǒng)計(jì)監(jiān)控的方法，我們稱之為?事后統(tǒng)計(jì)法。但是 這種 統(tǒng)計(jì)方法 有很大的局限性。 其表現(xiàn)在?兩個(gè)方面：
? ? ?1. 測(cè)試結(jié)果非常依賴測(cè)試環(huán)境， 比如測(cè)試環(huán)境的 硬件配置；
? ? ?2.測(cè)試結(jié)果受數(shù)據(jù)規(guī)模的影響很大，比如測(cè)試數(shù)據(jù)規(guī)模太小，測(cè)試結(jié)果可能無法真實(shí)的反應(yīng)算法的性能。
? ? 所以，我們需要一個(gè)不用具體的測(cè)試數(shù)據(jù)來測(cè)試，就可以粗略地估計(jì)算法的執(zhí)行效率的方法。這就是 時(shí)間、空間復(fù)雜度分析方法。
如何運(yùn)用復(fù)雜度分析：大O表示法
? ?大O表示法僅僅是一種粗略的分析模型，是一種估算，能幫助我們短時(shí)間內(nèi)了解一個(gè)算法的執(zhí)行效率。
? 如上圖代碼，假設(shè)我們?cè)O(shè)定每行代碼執(zhí)行的時(shí)間是?相同?的，都是單位時(shí)間 time, 那么上面的代碼執(zhí)行了多少個(gè) 單位時(shí)間呢？
? 首先，第一行和第二行代碼都執(zhí)行了 1遍，所以是 1 + 1 = 2 time;? 而第三行 和 第四行 執(zhí)行了 length 遍 ，length = n， 所以這兩行都 執(zhí)行了 n time， n + n = 2n time。
? 所以，這段代碼可以 粗略的得到 運(yùn)行的總時(shí)間 (2n + 2) time, 所以 代碼的執(zhí)行時(shí)間T(n) 和 每行代碼的執(zhí)行次數(shù)成 正比。
? ?再來看一段代碼
? ? 通過這兩段代碼執(zhí)行時(shí)間的推導(dǎo)過程，我們可以看到，所有代碼的執(zhí)行時(shí)間T(n)與每行代碼 的執(zhí)行次數(shù)n成正比。
? ? 我們可以將這個(gè)規(guī)律總結(jié)成一個(gè)公式，這就是我們所說的 大O表示法。
?? ? ? T(n) = O(f(n))
? ? T(n) 表示代碼執(zhí)行的時(shí)間；n 表示數(shù)據(jù)規(guī)模的大??；f(n)表示每行代碼執(zhí)行的次數(shù)總時(shí)間。因?yàn)檫@是一個(gè)公式，所以用f(n)來表示。公式中的O，表示代碼的執(zhí)行時(shí)間T(n)與f(n)表達(dá)式成正比。
? ? 上述的第一段代碼 可以 表示為 T(n) = O(2n + 2), 第二段 可以表示為??T(n) = O(2n^2+2n+2)。這就是 大O時(shí)間復(fù)雜度表示法。大O時(shí)間復(fù)雜度實(shí)際上并不具體表示代碼真正的執(zhí)行時(shí)間，而是表示代碼執(zhí)行時(shí)間隨數(shù)據(jù)規(guī)模增長的變化趨勢(shì)，所以，也叫作漸進(jìn)時(shí)間復(fù)雜度（asymptotic time complexity），簡稱時(shí)間復(fù)雜度。
? ?當(dāng)n很大時(shí)，你可以把它想象成10000、100000 甚至 無窮大。而公式中的低階、常量、系數(shù)三部分并不左右增長趨勢(shì)，所以都?可以忽略。我們只需要記錄一個(gè)?最大量級(jí)?就可以 了，如果用大O表示法表示剛講的那兩段代碼的時(shí)間復(fù)雜度，就可以記為：T(n) = O(n)； T(n) = O(n^2)。
時(shí)間復(fù)雜度如何分析
? ?1.只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
? ? ? 如上圖的代碼1， 當(dāng) n 無窮大的時(shí)候， 低階、常量、系數(shù)可以忽略不計(jì)，我們只用關(guān)心這個(gè) for 循環(huán)就可以了， 所以它的時(shí)間復(fù)雜度 就是 O(n)。
? ?2.加法法則：總復(fù)雜度 等于 量級(jí)最大?的那段代碼的復(fù)雜度
? ? ? ? 我們分析這段 代碼， 它的 時(shí)間復(fù)雜度 是 (2 + 2n + 2n^2) time， 當(dāng) n 是無窮大的時(shí)候， 我們?nèi)∑鹬辛考?jí)最大的， n^2, 所以 這段代碼的 時(shí)間復(fù)雜度 就是 O(n^2)。
? ? ? ? 總結(jié) :? 總的時(shí)間復(fù)雜度就等于量級(jí)最大的那段代碼的時(shí)間 復(fù)雜度。
? ? 3.乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積
? ? ? 理解了 加法法則，那么乘法法則就不難理解。
? ? 上面代碼 fun2 調(diào)用了 fun，fun2 的時(shí)間復(fù)雜度 就是 T1(n) * T2(n^2) = O(n) * O(n^2) = O(n^3)。
? ? ?總結(jié)：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積。
常見的時(shí)間復(fù)雜度
? ? 常見的復(fù)雜度量級(jí)有：常量階（O(1)）、對(duì)數(shù)階（O(logn)）、線性階（O(n)）、線性對(duì)數(shù)階（O(nlogn)）、平方、立方、k次方階（O(n^2)、O(n^3).........O(n^k)）、指數(shù)階（O(2^n)）、階乘階（O(n!)）。
? ? 上述復(fù)雜度量階可以?粗略的 分為兩類：多項(xiàng)式量級(jí)?和 非多項(xiàng)式量級(jí)。其中，非多項(xiàng)式量級(jí)只有兩個(gè)：O(2^n) 和 O(n!)。 當(dāng) n 越來越大時(shí)，非多項(xiàng)式量級(jí)就是 急劇的 增大， 執(zhí)行的時(shí)間就會(huì) 無限增長，因此，非多項(xiàng)式量級(jí) 是 效率很低的算法。
? ??O(1)
? ? ???O(1)? 表示的 不是 執(zhí)行了一行代碼，是?常量級(jí)?時(shí)間復(fù)雜度的一種表示方法， 比如
? ? ? ? 雖然代碼有三行，但是 它的時(shí)間復(fù)雜度 也是 O(1)，只要代碼的執(zhí)行時(shí)間不隨 n 的增大而增長，這樣代碼的時(shí)間復(fù)雜度我們都記作 O(1)。或者說，一般情況下，只要算法中不存在循環(huán)語句、遞歸語句，即使有成千上萬行的代碼，其時(shí)間復(fù)雜度也是 Ο(1)。
? ?O(logn)、O(nlogn)
? ? ? ?對(duì)數(shù)階時(shí)間復(fù)雜度： 計(jì)算出上述代碼的執(zhí)行次數(shù)，我們就能得到它的時(shí)間復(fù)雜度，那么我們要如何計(jì)算呢。運(yùn)用高中的知識(shí)：
? ? ? ?2^0 * 2^1 * 2^2 *........2^x = n;
? ? ? x 就等于 log2(n), 所以它的時(shí)間復(fù)雜度就是?是 O(log2(n))， 采用大 O 表示法 我們可以忽略掉系數(shù)，所以不論是 log3(n),? 還是 log4(n)...... 它們的時(shí)間復(fù)雜度可以 統(tǒng)一的為 O(logn），那么 O(nlogn) 是 如何出現(xiàn)的，我們可以參考 上面的?乘法法則，如果一段代碼的時(shí)間復(fù)雜度是O(logn)，我們循環(huán)執(zhí)行 n 遍，時(shí)間復(fù)雜度就是 O(nlogn) 了。
空間復(fù)雜度分析
? ? 空間復(fù)雜度全稱 就是 漸進(jìn)空間復(fù)雜度（asymptotic space complexity），表示算法的存儲(chǔ)空間（額外的內(nèi)存消耗）與數(shù)據(jù)規(guī)模之間的增長關(guān)系。
? ??如當(dāng)一個(gè)算法的空間復(fù)雜度為一個(gè)常量，即不隨被處理數(shù)據(jù)量n的大小而改變時(shí)，可表示為O(1)；當(dāng)一個(gè)算法的空間復(fù)雜度與 n 成線性比例關(guān)系時(shí)，可表示為 O(n)
? ??我們常見的空間復(fù)雜度就是O(1)、O(n)、O(n^2 )，空間復(fù)雜度 比 時(shí)間復(fù)雜度 簡單一些。
