xwzz.jpg

重溫：數(shù)據(jù)結(jié)構(gòu)與算法 - 開篇

前章提到漂羊，為了提高代碼質(zhì)量藤韵，需要選擇正確的數(shù)據(jù)結(jié)構(gòu)與算法，就需考量代碼的執(zhí)行效率和資源消耗兩個(gè)方面撕攒。

本章主要學(xué)習(xí)考量代碼執(zhí)行效率（時(shí)間）咬像、資源消耗（空間）的方式方法。

事后分析法

首先疚脐，性能測試亿柑、時(shí)間統(tǒng)計(jì)、內(nèi)存監(jiān)控等方案可以直觀的讓我們看到時(shí)間與空間的使用情況棍弄，并且得到確切值望薄。

但以上方案都有以下局限性：

• 1疟游、測試結(jié)果依賴測試環(huán)境

隨著測試環(huán)境的硬件不同，得到的測試結(jié)果差距也就越大式矫。eg：i9 cpu 和 i3 cpu 執(zhí)行同一段代碼時(shí)乡摹，很明顯i9所用的時(shí)間要小i3.

• 2、測試結(jié)果隨數(shù)據(jù)規(guī)模的變化可能產(chǎn)出完全不一的結(jié)果

例如我們在做排序的時(shí)候采转，數(shù)據(jù)規(guī)模足夠大快速排序優(yōu)于插入排序聪廉；但如果數(shù)據(jù)規(guī)模很小，插入排序反倒會(huì)比快速排序要快（后面的章節(jié)會(huì)細(xì)講）故慈。

• 3板熊、后滯性

我們只有在進(jìn)行完測試后才能知道現(xiàn)在的算法是否優(yōu)于之前的算法。

所以察绷，有沒有一種方法可以在不需要測試數(shù)據(jù)的情況下干签，就能 粗略估算 出當(dāng)前代碼的執(zhí)行效率和資源消耗？

大O復(fù)雜度表示法

例子1.png

想必這段代碼拆撼，大家都不陌生容劳，求1+2+3+...+n的累加和。

我們開始嘗試分析這段代碼闸度，先假設(shè)一個(gè)前提竭贩，代碼的執(zhí)行效率粗略的比作代碼的執(zhí)行時(shí)間，每行代碼的執(zhí)行完成的時(shí)間都一樣莺禁，都占用一個(gè)單位時(shí)間留量，記作：unitTime.

那么，我們嘗試以“肉眼”的形式來估算這段代碼的執(zhí)行時(shí)間哟冬，并在注釋中標(biāo)出每行代碼執(zhí)行時(shí)間：

int sum = 0;            // 1 * unitTime（執(zhí)行 1 次）
int i = 1;              // 1 * unitTime（執(zhí)行 1 次）
for (; i <= n; i++) {   // n * unitTime（執(zhí)行 n 次）
    sum += i;           // n * unitTime（執(zhí)行 n 次）
}

執(zhí)行總時(shí)間 = (1+1+n+n) * unitTime = (2+2n) * unitTime

如果用數(shù)學(xué)函數(shù)來表達(dá)這個(gè)公式：

• T(n) 表示 代碼的執(zhí)行總時(shí)間
• f(n) 表示代碼的執(zhí)行總次數(shù)

則：

f(n) = 2 +2n
T(n) = (2+2n) * unitTime = f(n) * unitTime

重點(diǎn)來了楼熄，這里引入一個(gè)復(fù)雜度分析概念：

當(dāng)n取值趨近于無窮大時(shí)，f(n)的常數(shù)項(xiàng)和系數(shù)項(xiàng)相比于n的取值規(guī)模對(duì)整個(gè)函數(shù)的影響可以忽略不計(jì)浩峡，僅需關(guān)注函數(shù)的最大階可岂。

什么意思呢？拿上面的例子來說翰灾，n的取值無限大時(shí)缕粹，這段代碼的執(zhí)行時(shí)間也會(huì)成比的增長，反觀常數(shù)項(xiàng)2预侯、系數(shù)項(xiàng)2對(duì)整體的影響就小之又小，所以在估算復(fù)雜度時(shí)峰锁，我們往往省略影響小的部分萎馅，取影響最大的部分，則得到：

f(n)= 2+2n --> f(n) = n

這種分析方法虹蒋，稱之為“大O復(fù)雜度表示法”糜芳，有專門的公式來表示：

大O公式.png

最終飒货，這段累加和的示例代碼，以大O復(fù)雜度表示法來表示:

T(n) = O(fn) = O( 2+2n) = O(n)

時(shí)間復(fù)雜度

通過上面的例子峭竣，我們已經(jīng)計(jì)算出了累加和的代碼時(shí)間復(fù)雜度就是：O(n)塘辅。
總結(jié)下時(shí)間復(fù)雜度概念：

時(shí)間復(fù)雜度 并不表示代碼的實(shí)際執(zhí)行時(shí)間，而是代碼執(zhí)行時(shí)間與數(shù)據(jù)規(guī)模發(fā)生增長的變化趨勢皆撩，叫作 漸進(jìn)時(shí)間復(fù)雜度扣墩，簡稱：時(shí)間復(fù)雜度。

復(fù)雜度分析

知道了什么是時(shí)間復(fù)雜度扛吞，下面介紹幾種復(fù)雜度分析技巧：

• 1呻惕、執(zhí)行次數(shù)最多的那段代碼

還記得上面提到的復(fù)雜度分析概念嗎？當(dāng)n取值趨近于無窮大時(shí)滥比，f(n)的常數(shù)項(xiàng)和系數(shù)項(xiàng)相比于n的取值規(guī)模對(duì)整個(gè)函數(shù)的影響可以忽略不計(jì)亚脆，我們僅關(guān)注函數(shù)的最大階。

通過這個(gè)概念盲泛，分析一個(gè)算法時(shí)濒持，我們只需關(guān)注被執(zhí)行次數(shù)最多的那段代碼，這段代碼執(zhí)行次數(shù)n的量級(jí)寺滚，就是這個(gè)它的時(shí)間復(fù)雜度柑营。

int sum = 0;            // 1 * unitTime（執(zhí)行 1 次）
int i = 1;              // 1 * unitTime（執(zhí)行 1 次）
for (; i <= n; i++) {   // n * unitTime（執(zhí)行 n 次）
    sum += i;           // n * unitTime（執(zhí)行 n 次）
}

累加和這個(gè)例子中，我們一眼看過去執(zhí)行最多次的代碼玛迄，就是for循環(huán)中的代碼由境，并且執(zhí)行次數(shù)隨著n的改變而變化，所以它的時(shí)間復(fù)雜度就是：O(n)

再練習(xí)一個(gè)例子：

public int fun2(int n) {
    int sum = 0;                // 1 * unitTime
    int i = 1;                  // 1 * unitTime
    int j;                      // 1 * unitTime
    for (; i <= n; i++) {       // n * unitTime
        j = 1;                  // n * unitTime
        for (; j <= n; j++) {   // n2 * unitTime
            sum = sum + i * j;  // n2 * unitTime
        }
    }
    return sum;
}

我們還是標(biāo)出每行代碼的執(zhí)行次數(shù)蓖议，會(huì)得到總次數(shù)為：

f(n)=3+2n+2n2

不過虏杰，我們知道了時(shí)間復(fù)雜度等于執(zhí)行次數(shù)最多的那段代碼n的量級(jí)，所以一眼就能看出它的時(shí)間復(fù)雜度是：O(n2）.

• 2勒虾、加法法則：總復(fù)雜度等于量級(jí)最大的那段代碼復(fù)雜度

有時(shí)候纺阔，代碼中出現(xiàn)多個(gè)時(shí)間復(fù)雜度的情況，例如：

public int fun3(int n) {
//1修然、第一段
    int sum1 = 0;
    int i = 1;
    for (; i <= 100; i++) {
        sum1 += i;    // 100 * unitTime
    }
    
//2笛钝、第二段
    int sum2 = 0;
    int j = 1;
    for (; j <= n; j++) {
        sum2 += j;   // n * unitTime
    }
    
//3、第三段
    int sum3 = 0;
    int k = 1;
    int l;
    for (; k <= n; k++) {
        l = 1;
        for (; l <= n; l++) {
            sum3 = sum3 + i * j;  // n2 * unitTime
        }
    }
    return sum1 + sum2 + sum3;
}

很明顯愕宋，這里有三段代碼的時(shí)間復(fù)雜度玻靡，我們分別為：

T1(n) = O(1)
T2(n) = O(n)
T3(n) = O(n2)

后面兩段代碼的時(shí)間復(fù)雜度根據(jù)執(zhí)行次數(shù)最多的那段代碼準(zhǔn)則， 一眼可看出是O(n)和O(n2)中贝；
第一個(gè)為什么是O(1)而不是O(100)囤捻，在這里說明下，前面概念提到過時(shí)間復(fù)雜度不是指代碼的實(shí)際執(zhí)行時(shí)間或次數(shù)邻寿，而是指兩者之間的增長趨勢蝎土，在這里面無論n如何增長视哑，第一段代碼的執(zhí)行次數(shù)都是不會(huì)受到影響的，對(duì)于這種常量階的時(shí)間復(fù)雜度誊涯，統(tǒng)統(tǒng)記為：O(1).

回歸正題挡毅，上面這三段代碼都有自己的時(shí)間復(fù)雜度，那整個(gè)算法的時(shí)間復(fù)雜度可以通過 加法法則：取最大階 的方式獲得：

T(n) = T1(n) + T2(n )+ T3(n) = max( O(1) , O(n) , O(n2) ) = O(n2)

• 3暴构、乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積

根據(jù)描述可以看出這個(gè)法則適用于嵌套代碼跪呈，那什么是嵌套代碼？

其實(shí)fun2()的例子就是嵌套代碼丹壕，只是我們一眼就看出第二層for循環(huán)里的代碼執(zhí)行次數(shù)為n2次庆械，很多情況下代碼并不能直觀的讓我們看到它的最大階，例如這個(gè)例子的代碼稍微改一下：

public int fun4(int n) {
    int sum = 0;
    int i = 1;
    for (; i <= n; i++) {
        sum = sum + fun5(n, i); // n * unitTime
    }
    return sum;
}

public int fun5(int n, int i) {
    int sum = 0;
    int j = 1;
    for (; j <= n; j++) {
        sum = sum + j * i;      // n * unitTime
    }
    return sum;
}

我們只是把第二層循環(huán)放到了新的方法中菌赖，由于n在兩個(gè)代碼片段中缭乘，我們很難一眼看到n的最大階，此時(shí)我們只需把嵌套內(nèi)外代碼都看成獨(dú)立的代碼片段琉用，算出各自的時(shí)間復(fù)雜度后堕绩，做乘積即可：

T1(n) = O(n)
T2(n) = O(n)
T(n) = T1(n) * T2(n) = O(n) * O(n) = O(n*n) = O(n2)

以上就是常用的3種復(fù)雜度分析的方法，至于實(shí)際問題中使用哪種邑时，只有多練習(xí)奴紧，熟能生巧。

常見的時(shí)間復(fù)雜度

雖然代碼千差萬別晶丘，但實(shí)際上常見的復(fù)雜度量級(jí)并不多黍氮。我們已經(jīng)了解了3種常見的時(shí)間復(fù)雜度：

• 常量階 O(1)
• 線性階 O(n)
• 次方階 O(n2)

既然我們嵌套兩層n循環(huán)時(shí)間復(fù)雜度是O(n2)，三層則為O(n3),同理無論多少次方我們統(tǒng)稱為次方階浅浮。

除了這3種沫浆，還有：

• 對(duì)數(shù)階 O(logn)

對(duì)數(shù)的概念還記得？（高中數(shù)學(xué)）滚秩，比如：32 = 9 以對(duì)數(shù)的形式表示就是 2 = log9 专执，讀作：2是以3為底，9的對(duì)數(shù)郁油；那么x = logN本股，讀作：x是以a為底N的對(duì)數(shù)。

知道了對(duì)數(shù)的基本概念后桐腌，什么樣的代碼是對(duì)數(shù)階呢拄显？

public void fun6(int n) {
    int i = 1;
    while (i <= n) {
        i = i * 2;      // ? * unitTime
    }
}

也是一段很常見的代碼，怎么證明它是對(duì)數(shù)階呢案站？

很明顯我們只要計(jì)算出
i = i * 2
這行代碼的執(zhí)行次數(shù)與n之間關(guān)系躬审，就可得到它的時(shí)間復(fù)雜度

我們可以嘗試給n帶入一批測試數(shù)據(jù)，比如n=4時(shí)：

i=1  i = 1 * 2 = 2
i=2  i = 2 * 2 = 4
i=4  i = 4 * 2 = 8

n=10時(shí)：

i=1  i = 1 * 2 = 2
i=2  i = 2 * 2 = 4
i=4  i = 4 * 2 = 8
i=8  i = 8 * 2 = 16     

我們會(huì)發(fā)現(xiàn)i的取值范圍是個(gè)等比數(shù)列：2 22 23 ... 2的x次方 ，當(dāng)2的x次方 > N 時(shí)停止循環(huán) 盒件， 那么我們就可以得到：f(n) = log2n.

通過換底公式我們可以繼續(xù)推算： f(n) = logn = logn / log2 = logn => logn

我們把對(duì)數(shù)形式的時(shí)間復(fù)雜度的底數(shù)都換為以10為底，那么就會(huì)得到logn除以某個(gè)對(duì)數(shù)常數(shù) 舱禽，而大O復(fù)雜度表示法中我們忽略常數(shù)部分的影響炒刁，最終所有的對(duì)數(shù)復(fù)雜度都為： T(n) = O(logn)

• 線性對(duì)數(shù)階 O(nlogn)

如果前面的對(duì)數(shù)階已經(jīng)了解，那么在對(duì)數(shù)階的外層再加一層遍歷n次誊稚，利用乘法法則它的時(shí)間復(fù)雜度便是：T(n) = O(n) * O(logn) = O(nlogn)翔始，后續(xù)的歸并排序，快速排序復(fù)雜度都是O(nlogn)里伯，到對(duì)應(yīng)章節(jié)時(shí)再細(xì)說城瞎。

• 指數(shù)階(2的n次方) & 階乘階(n!)

這兩種稱之為非多項(xiàng)式量級(jí)，其它的稱之為多項(xiàng)式量級(jí)疾瓮。
非多項(xiàng)式算法脖镀，我們只需知道隨著n的增大，算法執(zhí)行時(shí)間會(huì)急劇增加狼电，是一種非常低效的算法蜒灰，實(shí)際開發(fā)中需避免出現(xiàn)這種代碼。

• O(m+n)

這是一種特殊的時(shí)間復(fù)雜度表示形式肩碟，之前的示例代碼都很理想强窖，一個(gè)算法中只存在一個(gè)數(shù)據(jù)n在影響代碼的執(zhí)行時(shí)間，但往往我們代碼會(huì)是這樣的：

public int fun7(int n, int m) {
    int sum1 = 0;
    int i = 1;
    for (; i < n; i++) {
        sum1 = sum1 + i;
    }

    int sum2 = 0;
    int j = 1;
    for (; i < m; j++) {
        sum2 = sum2 + j;
    }
    return sum1 + sum2;
}

出現(xiàn)了兩個(gè)量級(jí)：T1(n) = O(n)削祈、T2(m) = O(m)翅溺，這種情況下我們不能利用加法法則省略一個(gè)低階量級(jí)（m、n的量級(jí)相同）髓抑，所以它的時(shí)間復(fù)雜度：T(n) = T1(n) + T2（m）= O(n+m)

但如果是嵌套關(guān)系咙崎，乘法法則依舊是可用的，記作：O(m * n)

空間復(fù)雜度

前面長篇大論講解時(shí)間復(fù)雜度启昧，只要牢牢掌握它叙凡，空間復(fù)雜度相對(duì)簡單多了，因?yàn)闊o論是空間復(fù)雜度分析密末，還是常見的空間復(fù)雜度握爷，它們都是類似的。

重溫下時(shí)間復(fù)雜度概念：時(shí)間復(fù)雜度并不表示代碼的實(shí)際執(zhí)行時(shí)間严里，而是代碼執(zhí)行時(shí)間與數(shù)據(jù)規(guī)模發(fā)生增長的變化趨勢新啼；

類比一下，總結(jié)出空間復(fù)雜度的概念：

空間復(fù)雜度也并不表示實(shí)際的內(nèi)存存儲(chǔ)大小刹碾，而是內(nèi)存空間與數(shù)據(jù)規(guī)模增長的變化趨勢燥撞。

寫個(gè)簡單例子就明白了：

public void fun8(int n) {
    int[] arr = new int[n]; // n * unitSize
    int i = 0;              // 1 * unitSize
    for (; i < n; i++) {
        arr[i] = i;
    }
}

分析方法跟之前是大致相同的，我們只關(guān)注內(nèi)存趨勢發(fā)生改變最大的代碼，以它的量級(jí)作為空間復(fù)雜度物舒，即：S(n)=O(n).

常見的空間復(fù)雜度

常見的空間復(fù)雜度一般有：

• O(1)
• O(n)
• O(n2)

像對(duì)數(shù)階色洞，線性對(duì)數(shù)階基本都用不到。

空間復(fù)雜度的內(nèi)容就不一一舉例了冠胯，只要多加練習(xí)火诸，真正理解了時(shí)間復(fù)雜度，空間復(fù)雜度自然迎刃而解荠察。

小結(jié)

復(fù)雜度也稱漸進(jìn)復(fù)雜度置蜀，可分為時(shí)間復(fù)雜度和空間復(fù)雜度，使用大O表示法來表示悉盆；
可以粗略的認(rèn)為盯荤，越高階的復(fù)雜度算法，性能越低焕盟；
常見的復(fù)雜度由低到高：O(1)秋秤、O(logn)、O(n)脚翘、O(nlogn)航缀、O(n2).

復(fù)雜度分析并不難，貴在練習(xí)堰怨！