終于開始寫數(shù)據(jù)結(jié)構(gòu)和算法的博客了，邁出了2019年的第一步，今年的計劃，首先是寫完數(shù)據(jù)結(jié)構(gòu)和算法的博客，然后開始學(xué)習(xí)Android源碼，另外，小程序，flutter，kotlin也開始要學(xué)起來，學(xué)習(xí)的中途，也會做自己的項目，是一個MVP+retrofit+rxjava+dagger2的項目，另外，公司的項目已經(jīng)截止，接的私活開始做起來，買了扔物線的HencoderPlus，兩個月學(xué)完，今年是很忙的一年，也是會進(jìn)步巨大的一年。今年加薪50%跳槽，是一個非常不錯的開始，希望下一次跳槽，能有更大的漲幅，加油吧！

要分析數(shù)據(jù)結(jié)構(gòu)和算法，離不開復(fù)雜度的分析，復(fù)雜度分析包括：時間復(fù)雜度和空間復(fù)雜度。數(shù)據(jù)結(jié)構(gòu)和算法，解決的就是兩個問題，第一：如何讓代碼運(yùn)行的更快；第二：如何讓代碼更節(jié)省空間。這兩個問題對應(yīng)的就是時間復(fù)雜度和空間復(fù)雜度。所以學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法，首先要學(xué)習(xí)的就是時間復(fù)雜度和空間復(fù)雜度的分析。

一、時間復(fù)雜度

1.1 大o復(fù)雜度表示法

首先，我們看下面一段代碼

public int sum(int n){
  int sum = 0; 
  int i = 1;
  for(; i < n;++i){
     sum = sum + I; 
   }
  return sum;
}

在這里，我們粗略估計，cpu在運(yùn)行這段代碼時，每一行代碼的執(zhí)行時間都相同為unit_time，（當(dāng)然，每一行代碼的運(yùn)行時間必然不相同，但這里我們只是粗略的估計，視為每行代碼運(yùn)行時間都相同。）那么估算一下，這段代碼的運(yùn)行時間是多少呢？
我在下面的代碼塊里標(biāo)注出每行代碼的運(yùn)行時間：

public int sum(int n){
  int sum = 0; // 1 * unit_time
  int i = 1;// 1 * unit_time
  for(; i < n;++i){ // n * unit_time
     sum = sum + i; // n * unit_time
   }
  return sum; // 1 * unit_time
}

因此，我們可以算出，這段代碼總的運(yùn)行時間為：T(n) = （3+n+n）* unit_time。在這里，代碼執(zhí)行時間T(n)與代碼執(zhí)行次數(shù)n成正比。

再看下面這段稍微復(fù)雜一點(diǎn)的代碼：同樣的，我們依然假設(shè)CPU執(zhí)行每一行代碼的時間都是相同的為unit_time，在代碼塊中標(biāo)注出每一行代碼執(zhí)行的時間：

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

如上所示，可以算出，這段代碼執(zhí)行的總時間T(n) = （3 + n + n + n2 + n2 ）* unit_time ，這里，我們也可以得出一個結(jié)論，代碼執(zhí)行時間T(n)與執(zhí)行次數(shù)n成正比。也就是我們常說的大O復(fù)雜度表示法：

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

公式中，T(n)表示的是代碼執(zhí)行的總時間，n表示的是數(shù)據(jù)的規(guī)模，f(n)表示的是代碼執(zhí)行次數(shù)的總和，公式中的O表示代碼的執(zhí)行時間T(n)與f(n)成正比。

上面第一個例子和第二個例子使用大O時間復(fù)雜度表示法就可以表示成：
T(n) = O(（3+n+n）* unit_time) 和 T(n) = O( （3 + n + n + n2 + n2 ）* unit_time ) 這就是大O時間表示法。大O時間復(fù)雜度實(shí)際上并不具體表示代碼真正的執(zhí)行時間，而是代表代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢，所以，也叫做漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。
當(dāng)n很大時，公式中的低階、常量、系數(shù)三部分不能左右增長趨勢，都可以忽略，只需要記錄一個最大量級就可以了，上述兩個例子中，用大O復(fù)雜度表示，可以記為T(n) = O(n)和 T(n) = O(n2)

1.2 時間復(fù)雜度分析

了解了時間復(fù)雜度的概念，怎么分析一段代碼的時間復(fù)雜度呢？三個方法

1. 只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼。

2. 總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度。

3. 嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積。

1.2.1 幾種常見的時間復(fù)雜度分析

幾種常見的時間復(fù)雜度分析

常見的復(fù)雜度量級，可以粗略的分為兩類，多項式量級和非多項式量級。其中非多項式量級只有兩個：O(2的n次方) 和 O(n!)。當(dāng)數(shù)據(jù)規(guī)模越來越大時，非多項式量級算法的執(zhí)行時間會急劇增加，求解問題的執(zhí)行時間會無限增長，所以，非多項式量級的算法都是非常低效的算法，應(yīng)該盡量避免。我們來看幾種常見的多項式時間復(fù)雜度。

1.常量階時間復(fù)雜度 O(1)

只要代碼執(zhí)行時間不隨n的增大而增大，這樣的代碼的時間復(fù)雜度我們都記作O(1) ，一般情況下，只要算法中不存在循環(huán)語句、遞歸語句，即使有成千上萬條代碼，其時間復(fù)雜度也是O(1)。

2.對數(shù)階時間復(fù)雜度 O(logn)、O(nlogn)

對數(shù)階時間復(fù)雜度非常常見，看下面這段代碼：

  I=1;
 while (i <= n)  {
   i = i * 2;
 }

對上面這段代碼進(jìn)行分析：變量i的值從1開始取，每循環(huán)一次就乘以2。當(dāng)大于n時，循環(huán)結(jié)束。當(dāng)i < n時，i的值分別為 1、2、4、8、16....也就是2的n次方。

image.png

所以，我們只要知道x的值，就知道這段代碼的執(zhí)行次數(shù)了，x=log2n ，這段代碼的時間復(fù)雜度就是O(log2n)(2是底數(shù))，如果把這段代碼修改一下，改為：

  I=1;
 while (i <= n)  {
   i = i * 3;
 }

那么這段代碼的時間復(fù)雜度就是O(log3n)(3是底數(shù))，我們知道，對數(shù)之間是可以相互轉(zhuǎn)換的，log3n 就等于 log32 * log2n，其中l(wèi)og32是一個常數(shù)，我們前面分析得出的結(jié)論，在分析復(fù)雜度時，常數(shù)可以忽略，所以O(shè)(log2n) = O(log3n)，在對數(shù)階復(fù)雜度表示方法里，忽略對數(shù)的底，統(tǒng)一表示為：O(logn)。
如果一段代碼的時間復(fù)雜度是O(logn)，當(dāng)它循環(huán)執(zhí)行n次時，它的時間復(fù)雜度就是O(nlogn)。

3. O(m+n)、O(m*n)

我們先來看一段代碼：

int cal(int m, int n) {
  int sum_1 = 0;
  int i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + I;
  }

  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

從代碼中可以看出，m和n是兩個數(shù)據(jù)規(guī)模。在不知道m(xù)、n的值的情況下，無法事先評估m(xù)和n誰的量級大，所以在表示復(fù)雜度的時候，就不能簡單地利用加法法則，省略掉其中一個，此時時間復(fù)雜度就為：T1(n) + T2(m) = O(f(n) + g(m)) .

1.2.2 最好、最壞、平均、均攤時間復(fù)雜度

1 最好、最壞時間復(fù)雜度

先來看段代碼：

// n 表示數(shù)組 array 的長度
int find(int[] array, int n, int x) {
  int i = 0; //  1 * unit_time
  int pos = -1; // 1 * unit_time
  for (; i < n; ++i) { // n * unit_time
    if (array[i] == x) pos = I; // n * unit_time
  }
  return pos; // 1 * unit_time 
}

我們來分析下這段代碼的時間復(fù)雜度，這段代碼的目的是查詢x在數(shù)組中的位置，查找到之后，返回position，如果x不在數(shù)組中，返回-1。按照之前的學(xué)習(xí)的時間復(fù)雜度分析，我們可以知道的是，這段代碼的時間復(fù)雜度是O(n)。如果我們把這段代碼改進(jìn)一下，當(dāng)在數(shù)組中找到x后，中斷循環(huán)直接返回position。改進(jìn)后的代碼如下：

// n 表示數(shù)組 array 的長度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) { // 這句代碼運(yùn)行時間是多少個unit_time呢？
    if (array[i] == x) { 
       pos = I; 
       break;
    }
  }
  return pos;
}

這個時候，循環(huán)代碼執(zhí)行的次數(shù)和x在數(shù)組中的位置有關(guān)，如果x在數(shù)組中的第一個位置，那么循環(huán)只會執(zhí)行一次，這個情況就是最好的情況，那么它對應(yīng)的時間復(fù)雜度就是最好情況時間復(fù)雜度；如果x在數(shù)組最后一個位置，那么循環(huán)執(zhí)行n次，這個情況是最壞的情況，它對應(yīng)的時間復(fù)雜度就是最壞情況時間復(fù)雜度。

由此可以引出最好情況、最壞情況時間復(fù)雜度的概念。
最好情況時間復(fù)雜度：顧名思義，就是在最理想的情況下，執(zhí)行這段代碼的時間復(fù)雜度。上個例子中對應(yīng)的就是x在數(shù)組第一個位置時執(zhí)行這段代碼的時間復(fù)雜度。
最壞情況時間復(fù)雜度：在最壞的情況下，執(zhí)行這段代碼的時間復(fù)雜度。上個例子中對應(yīng)的就是x在數(shù)組最后一個位置時執(zhí)行這段代碼的時間復(fù)雜度。

2 平均情況時間復(fù)雜度

上面的例子，當(dāng)x在第一個位置或者x在最后一個位置這種極端情況其實(shí)并不常見，發(fā)生的概率并不大，事實(shí)上，x可以在數(shù)組中的任何位置，如果我們假設(shè)x在數(shù)組中位置的概率都一樣，都是1/n，另外還有一種可能是x不在數(shù)組中，所以，要查找x在數(shù)組中的位置，有n+1種情況。我們把每種情況下，查找需要遍歷的元素個數(shù)累加起來，然后再除以n+1，就可以得到需要遍歷的元素個數(shù)的平均值。

平均時間復(fù)雜度計算

但是這樣計算實(shí)際上是不準(zhǔn)確的，因?yàn)檫@n+1種情況，出現(xiàn)的概率并不一樣，x在數(shù)組中和不在數(shù)組中，概率為1/2。另外，要查找的數(shù)據(jù)出現(xiàn)在0 - n-1 這n個位置的概率也是一樣的，為1/n，根據(jù)概率乘法法則，要查找的數(shù)據(jù)出現(xiàn)0 - n-1 中任意位置的概率是1/2n。

如果將各種情況發(fā)生的概率都統(tǒng)計進(jìn)去的話，平均時間復(fù)雜度要這么計算：

加權(quán)平均時間復(fù)雜度

這個值就是概率論中的加權(quán)平均值，也叫作期望值，所以平均時間復(fù)雜度的全稱叫做加權(quán)平均時間復(fù)雜度或者期望時間復(fù)雜度。
可以看到，這段代碼的加權(quán)平均值是(3n+1)/4，用大O表示法來表示，去掉系數(shù)和常量，這段代碼的加權(quán)平均時間復(fù)雜度是O(n)。

在大多數(shù)情況下，我們并不需要區(qū)分最好最壞平均情況時間復(fù)雜度三種情況，很多時候只需要一個復(fù)雜度久夠了。除非一段代碼在不同情況下，時間復(fù)雜度有量級的差距，我們才需要使用這三種復(fù)雜度來區(qū)分。

1.3 空間復(fù)雜度分析

空間復(fù)雜度全稱是漸進(jìn)空間復(fù)雜度，表示算法存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。
看下面這段代碼：

void print(int n) {
  int i = 0;  //申請了一個存儲變量空間 
  int[] a = new int[n]; //申請了n個存儲變量空間
  for (i; i <n; ++i) {
    a[i] = i * I;
  }

  for (i = n-1; i >= 0; --i) {
    print out a[I]
  }
}

除了標(biāo)注的兩行代碼，其他代碼都沒有占用多少空間，所以整段代碼的空間復(fù)雜度就是O(n)。常見的空間復(fù)雜度一般就是O(1)，O(n)，O(n2)。