數(shù)據(jù)結(jié)構(gòu)就是指一組數(shù)據(jù)的存儲結(jié)構(gòu)。

算法就是操作數(shù)據(jù)的一組方法。

從狹義上講

是指某些著名的數(shù)據(jù)結(jié)構(gòu)和算法，比如隊列、棧、堆、二分查找、動態(tài)規(guī)劃等

數(shù)據(jù)結(jié)構(gòu)和算法關(guān)系

數(shù)據(jù)結(jié)構(gòu)是為算法服務(wù)的，算法要作用在特定的數(shù)據(jù)結(jié)構(gòu)之上

比如，因為數(shù)組具有隨機(jī)訪問的特點，常用的二分查找算法需要用數(shù)組來存儲數(shù)據(jù)。但如果我們選擇鏈表這種數(shù)據(jù)結(jié)構(gòu)，二分查找算法就無法工作了，因為鏈表并不支持隨機(jī)訪問

復(fù)雜度分析

事后統(tǒng)計法的局限性

1. 測試結(jié)果非常依賴測試環(huán)境

測試環(huán)境中硬件的不同會對測試結(jié)果有很大的影響

2. 測試結(jié)果受數(shù)據(jù)規(guī)模的影響很大

對于小規(guī)模的數(shù)據(jù)排序，插入排序可能反倒會比快速排序要快

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

 int cal(int n) {   int sum = 0;   int i = 1;   int j = 1;   for (; i <= n; ++i) {     j = 1;     for (; j <= n; ++j) {       sum = sum +  i * j;     }   } }

公式：

上邊例子可表示為T(n) = O(2n^2+2n+3)

大 O 時間復(fù)雜度實際上并不具體表示代碼真正的執(zhí)行時間，而是表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢，所以，也叫作漸進(jìn)時間復(fù)雜度（asymptotic time complexity），簡稱時間復(fù)雜度。

常量級時間

即便這段代碼循環(huán) 10000 次、100000 次，只要是一個已知的數(shù)，跟 n 無關(guān)，照樣也是常量級的執(zhí)行時間

時間復(fù)雜度分析

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

忽略掉公式中的常量、低階、系數(shù)，只需要記錄一個最大階的量級就可以了

我們在分析一個算法、一段代碼的時間復(fù)雜度的時候，也只關(guān)注循環(huán)執(zhí)行次數(shù)最多的那一段代碼就可以了。這段核心代碼執(zhí)行次數(shù)的 n 的量級，就是整段要分析代碼的時間復(fù)雜度。

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

1. 第 2、3 行代碼都是常量級的執(zhí)行時間，與 n 的大小無關(guān)，所以對于復(fù)雜度并沒有影響。

2. 循環(huán)執(zhí)行次數(shù)最多的是第 4、5 行代碼，所以這塊代碼要重點分析。這兩行代碼被執(zhí)行了 n 次，所以總的時間復(fù)雜度就是 O(n)

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

int cal(int n) {   int sum_1 = 0;   int p = 1;   for (; p < 100; ++p) {     sum_1 = sum_1 + p;   }
   int sum_2 = 0;   int q = 1;   for (; q < n; ++q) {     sum_2 = sum_2 + q;   }    int sum_3 = 0;   int i = 1;   int j = 1;   for (; i <= n; ++i) {     j = 1;      for (; j <= n; ++j) {       sum_3 = sum_3 +  i * j;     }   }    return sum_1 + sum_2 + sum_3; }

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

落實到具體的代碼上，我們可以把乘法法則看成是嵌套循環(huán)

int cal(int n) {   int ret = 0;    int i = 1;   for (; i < n; ++i) {     ret = ret + f(i);   }  }   int f(int n) {  int sum = 0;  int i = 1;  for (; i < n; ++i) {    sum = sum + i;  }   return sum; }

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

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

要代碼的執(zhí)行時間不隨 n 的增大而增長，這樣代碼的時間復(fù)雜度我們都記作 O(1)。

只要算法中不存在循環(huán)語句、遞歸語句，即使有成千上萬行的代碼，其時間復(fù)雜度也是Ο(1)。

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

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

變量 i 的值從 1 開始取，每循環(huán)一次就乘以 2。當(dāng)大于 n 時

變量 i 的取值就是一個等比數(shù)列

3. O(m+n)、O(m*n)由兩個數(shù)據(jù)的規(guī)模來決定

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;
}

復(fù)制代碼

上面代碼的時間復(fù)雜度就是 O(m+n)

空間復(fù)雜度分析（只計算與n有關(guān)的內(nèi)存空間）

空間復(fù)雜度全稱就是漸進(jìn)空間復(fù)雜度（asymptotic space complexity），表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系

常見的空間復(fù)雜度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 這樣的對數(shù)階復(fù)雜度平時都用不到

void print(int n) {  int i = 0;  int[] a = new int[n];  for (i; i <n; ++i) {    a[i] = i * i;  }
  for (i = n-1; i >= 0; --i) {    print out a[i]  }}

第 2 行代碼中，我們申請了一個空間存儲變量 i，但是它是常量階的，跟數(shù)據(jù)規(guī)模 n 沒有關(guān)系，所以我們可以忽略。

第 3 行申請了一個大小為 n 的 int 類型數(shù)組，除此之外，剩下的代碼都沒有占用更多的空間，所以整段代碼的空間復(fù)雜度就是 O(n)。

總結(jié)

復(fù)雜度也叫漸進(jìn)復(fù)雜度，包括時間復(fù)雜度和空間復(fù)雜度，用來分析算法執(zhí)行效率與數(shù)據(jù)規(guī)模之間的增長關(guān)系，可以粗略地表示，越高階復(fù)雜度的算法，執(zhí)行效率越低

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

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

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

上面 這段代碼的復(fù)雜度是 O(n)，其中，n 代表數(shù)組的長度

int find(int[] array, int n, int x) {  int i = 0;  int pos = -1;  for (; i < n; ++i) {    if (array[i] == x) {       pos = i;       break;  //加入了break    }  }  return pos;}

上邊的代碼 如果數(shù)組中第一個元素正好是要查找的變量 x，那就不需要繼續(xù)遍歷剩下的 n-1 個數(shù)據(jù)了，那時間復(fù)雜度就是 O(1)。

但如果數(shù)組中不存在變量 x，那我們就需要把整個數(shù)組都遍歷一遍，時間復(fù)雜度就成了 O(n)。所以，不同的情況下，這段代碼的時間復(fù)雜度是不一樣的。

最好情況時間復(fù)雜度就是，在最理想的情況下，執(zhí)行這段代碼的時間復(fù)雜度

最壞情況時間復(fù)雜度就是，在最糟糕的情況下，執(zhí)行這段代碼的時間復(fù)雜度

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

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

假設(shè)在數(shù)組中與不在數(shù)組中的概率都為 1/2。

另外，要查找的數(shù)據(jù)出現(xiàn)在 0～n-1 這 n 個位置的概率也是一樣的，為 1/n。

所以，根據(jù)概率乘法法則，要查找的數(shù)據(jù)出現(xiàn)在 0～n-1 中任意位置的概率就是 1/(2n)

這個值就是概率論中的加權(quán)平均值，也叫作期望值，

所以平均時間復(fù)雜度的全稱應(yīng)該叫加權(quán)平均時間復(fù)雜度或者期望時間復(fù)雜度。

用大 O 表示法來表示，去掉系數(shù)和常量，這段代碼的加權(quán)平均時間復(fù)雜度仍然是 O(n)。

大多數(shù)情況下，我們并不需要區(qū)分最好、最壞、平均情況時間復(fù)雜度三種情況

只有同一塊代碼在不同的情況下，時間復(fù)雜度有量級的差距，我們才會使用這三種復(fù)雜度表示法來區(qū)分

均攤時間復(fù)雜度

攤還分析法，通過攤還分析得到的時間復(fù)雜度我們起了一個名字，叫均攤時間復(fù)雜度。

 // array表示一個長度為n的數(shù)組 // 代碼中的array.length就等于n int[] array = new int[n]; int count = 0;  void insert(int val) {    if (count == array.length) {       int sum = 0;       for (int i = 0; i < array.length; ++i) {          sum = sum + array[i];       }       array[0] = sum;       count = 1;    }
    array[count] = val;    ++count; }

這段代碼實現(xiàn)了一個往數(shù)組中插入數(shù)據(jù)的功能。

當(dāng)數(shù)組滿了之后，也就是代碼中的 count == array.length 時，我們用 for 循環(huán)遍歷數(shù)組求和，并清空數(shù)組，將求和之后的 sum 值放到數(shù)組的第一個位置

然后再將新的數(shù)據(jù)插入。但如果數(shù)組一開始就有空閑空間，則直接將數(shù)據(jù)插入數(shù)組

最理想的情況下，數(shù)組中有空閑空間，我們只需要將數(shù)據(jù)插入到數(shù)組下標(biāo)為 count 的位置就可以了，所以最好情況時間復(fù)雜度為 O(1)

最壞的情況下，數(shù)組中沒有空閑空間了，我們需要先做一次數(shù)組的遍歷求和，然后再將數(shù)據(jù)插入，所以最壞情況時間復(fù)雜度為 O(n)

平均時間復(fù)雜度是O(1): 假設(shè)數(shù)組的長度是 n，根據(jù)數(shù)據(jù)插入的位置的不同，我們可以分為 n 種情況，每種情況的時間復(fù)雜度是 O(1)。除此之外，還有一種“額外”的情況，就是在數(shù)組沒有空閑空間時插入一個數(shù)據(jù)，這個時候的時間復(fù)雜度是 O(n)。而且，這 n+1 種情況發(fā)生的概率一樣，都是 1/(n+1)。所以，根據(jù)加權(quán)平均的計算方法，我們求得的平均時間復(fù)雜度就是：

O(n) 的插入操作 就是 最壞的情況下 求和清空插入 O(1) 的插入操作 就是 最理想的情況下 直接插入

每一次 O(n) 的插入操作，都會跟著 n-1 次 O(1) 的插入操作，所以把耗時多的那次操作均攤到接下來的 n-1 次耗時少的操作上，均攤下來，這一組連續(xù)的操作的均攤時間復(fù)雜度就是 O(1)，這就是均攤分析的大致思路

在能夠應(yīng)用均攤時間復(fù)雜度分析的場合，一般均攤時間復(fù)雜度就等于最好情況時間復(fù)雜度。

// 全局變量，大小為10的數(shù)組array，長度len，下標(biāo)i。int array[] = new int[10]; int len = 10;int i = 0;
// 往數(shù)組中添加一個元素void add(int element) {   if (i >= len) { // 數(shù)組空間不夠了     // 重新申請一個2倍大小的數(shù)組空間     int new_array[] = new int[len*2];     // 把原來array數(shù)組中的數(shù)據(jù)依次copy到new_array     for (int j = 0; j < len; ++j) {       new_array[j] = array[j];     }     // new_array復(fù)制給array，array現(xiàn)在大小就是2倍len了     array = new_array;     len = 2 * len;   }   // 將element放到下標(biāo)為i的位置，下標(biāo)i加一   array[i] = element;   ++i;}