重要性

復(fù)雜度分析是整個(gè)算法學(xué)習(xí)的精髓，只要掌握了它，數(shù)據(jù)結(jié)構(gòu)和算法的內(nèi)容基本上就掌握了一半。

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

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

我們需要一個(gè)不用具體的測(cè)試數(shù)據(jù)來測(cè)試，就可以粗略地估計(jì)算法的執(zhí)行效率的方法。

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

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

第 2、3 行代碼分別需要 1 個(gè) unit_time 的執(zhí)行時(shí)間，第 4、5 行都運(yùn)行了 n 遍，所以需要 2nunit_time 的執(zhí)行時(shí)間，所以這段代碼總的執(zhí)行時(shí)間就是 (2n+2)unit_time。可以看出來，所有代碼的執(zhí)行時(shí)間 T(n) 與每行代碼的執(zhí)行次數(shù)成正比。

所有代碼的執(zhí)行時(shí)間 T(n) 與每行代碼的執(zhí)行次數(shù) n 成正比。

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

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

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

   我們?cè)诜治鲆粋€(gè)算法、一段代碼的時(shí)間復(fù)雜度的時(shí)候，也只關(guān)注循環(huán)執(zhí)行次數(shù)最多的那一段代碼就可以了。

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

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

空間復(fù)雜度分析

時(shí)間復(fù)雜度的全稱是 漸進(jìn)時(shí)間復(fù)雜度，表示算法的執(zhí)行時(shí)間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。類比一下，空間復(fù)雜度全稱就是漸進(jìn)空間復(fù)雜度，表示算法的存儲(chǔ)空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。

復(fù)雜度種類

1. 最好情況時(shí)間復(fù)雜度

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

2. 最壞情況時(shí)間復(fù)雜度

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

3. 平均情況時(shí)間復(fù)雜度

4. 均攤時(shí)間復(fù)雜度

例子：

// 全局變量，大小為 10 的數(shù)組 array，長度 len，下標(biāo) i。
int array[] = new int[10]; 
int len = 10;
int i = 0;

// 往數(shù)組中添加一個(gè)元素
void add(int element) {
   if (i >= len) { // 數(shù)組空間不夠了
     // 重新申請(qǐng)一個(gè) 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;
}

最好 ，最壞 ，平均 ，均攤

參考自極客時(shí)間