釋義

1.數(shù)據(jù)結(jié)構(gòu)和算法解決是“如何讓計算機更快時間卧抗、更省空間的解決問題”序愚。
2.因此需從執(zhí)行時間和占用空間兩個維度來評估數(shù)據(jù)結(jié)構(gòu)和算法的性能。
3.分別用時間復(fù)雜度和空間復(fù)雜度兩個概念來描述性能問題茫船，二者統(tǒng)稱為復(fù)雜度近速。
4.復(fù)雜度描述的是算法執(zhí)行時間（或占用空間）與數(shù)據(jù)規(guī)模的增長關(guān)系。

時間均牢、空間復(fù)雜度分析：粗略地估計算法的執(zhí)行效率的方法糠雨，算法的執(zhí)行效率就是算法代碼執(zhí)行的時間

原因

1.和性能測試相比，復(fù)雜度分析有不依賴執(zhí)行環(huán)境徘跪、成本低甘邀、效率高砂竖、易操作、指導(dǎo)性強的特點鹃答。
2.掌握復(fù)雜度分析乎澄，將能編寫出性能更優(yōu)的代碼，有利于降低系統(tǒng)開發(fā)和維護成本测摔。

復(fù)雜度分析

大O表示法

1置济、來源

算法的執(zhí)行時間與每行代碼的執(zhí)行次數(shù)成正比，用T(n) = O(f(n))表示锋八，其中T(n)表示算法執(zhí)行總時間浙于，f(n)表示每行代碼執(zhí)行總次數(shù)，而n往往表示數(shù)據(jù)的規(guī)模挟纱。

2羞酗、特點

以時間復(fù)雜度為例，由于時間復(fù)雜度描述的是算法執(zhí)行時間與數(shù)據(jù)規(guī)模的增長變化趨勢紊服，所以常量階檀轨、低階以及系數(shù)實際上對這種增長趨勢不產(chǎn)生決定性影響，所以在做時間復(fù)雜度分析時忽略這些項欺嗤。

復(fù)雜度分析法則

1）單段代碼看高頻：比如循環(huán)参萄。
2）多段代碼取最大：比如一段代碼中有單循環(huán)和多重循環(huán)，那么取多重循環(huán)的復(fù)雜度煎饼。
3）嵌套代碼求乘積：比如遞歸讹挎、多重循環(huán)等
4）多個規(guī)模求加法：比如方法有兩個參數(shù)控制兩個循環(huán)的次數(shù)，那么這時就取二者復(fù)雜度相加吆玖。

常用的復(fù)雜度級別

time.jpg

多項式階：隨著數(shù)據(jù)規(guī)模的增長筒溃，算法的執(zhí)行時間和空間占用，按照多項式的比例增長沾乘。包括：
O(1)（常數(shù)階）怜奖、O(logn)（對數(shù)階）、O(n)（線性階）意鲸、O(nlogn)（線性對數(shù)階）烦周、O(n²)（平方階）尽爆、 O(n³)（立方階）
非多項式階：隨著數(shù)據(jù)規(guī)模的增長怎顾，算法的執(zhí)行時間和空間占用暴增，這類算法性能極差漱贱。包括：
O(2ⁿ)（指數(shù)階）槐雾、O(n!)（階乘階）

示例

假設(shè)每行代碼執(zhí)行的時間都一樣，為 unit_time幅狮。
1募强、O(n)

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

所有代碼的執(zhí)行時間為(2n+2)*unit_time
T(n) = O(2n+2)
當(dāng) n 很大時株灸，你可以把它想象成 10000、100000擎值。而公式中的低階慌烧、常量、系數(shù)三部分并不左右增長趨勢鸠儿，所以都可以忽略屹蚊。我們只需要記錄一個最大量級就可以了，用大 O 表示法表示进每，就可以記為：T(n) = O(n)汹粤；
2、O(n²)

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

T(n) = (2n²+2n+3)*unit_time, 即T(n) = O(n²)
3田晚、O(1)

 int i = 8;
 int j = 6;
 int sum = i + j;

一般情況下嘱兼，只要算法中不存在循環(huán)語句、遞歸語句贤徒，即使有成千上萬行的代碼芹壕，其時間復(fù)雜度也是Ο(1)。
4接奈、O(logn)哪雕、O(nlogn)

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

從代碼中可以看出，變量 i 的值從 1 開始取鲫趁，每循環(huán)一次就乘以 2斯嚎。當(dāng)大于 n 時，循環(huán)結(jié)束挨厚。變量 i 的取值就是一個等比數(shù)列堡僻。通過 2^x=n 求解 x(執(zhí)行次數(shù))，x=log₂n疫剃。時間復(fù)雜度就是 O(log₂n)钉疫。

log₃n 等于 log₃2 * log₂n，所以 O(log₃n) = O(C * log₂n)巢价，其中 C=log₃2 是一個常量牲阁。在采用大 O 標(biāo)記復(fù)雜度的時候，可以忽略系數(shù)壤躲，即 O(Cf(n)) = O(f(n))城菊。所以，O(log₂n) 就等于 O(log₃n)碉克。在對數(shù)階時間復(fù)雜度的表示方法里凌唬，我們忽略對數(shù)的“底”，統(tǒng)一表示為 O(logn)漏麦。

如果一段代碼的時間復(fù)雜度為O(logn)客税，循環(huán)執(zhí)行n遍后的時間復(fù)雜度就是O(nlogn)癞志。

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

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

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

int cal(int n) {
   int sum_1 = 0;
   int p = 1;
   for (; p < 100; ++p) { // 100
     sum_1 = sum_1 + p;
   }

   int sum_2 = 0;
   int q = 1;
   for (; q < n; ++q) { // n
     sum_2 = sum_2 + q;
   }
 
   int sum_3 = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) { // n^2
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }
 
   return sum_1 + sum_2 + sum_3;
 }

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

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

不同情況下的復(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;
}

在一個無序的數(shù)組（array）中闲昭，查找變量 x 出現(xiàn)的位置唆涝。如果沒有找到罚渐，就返回 -1。復(fù)雜度是 O(n)秧均。優(yōu)化如下：

// 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;
    }
  }
  return pos;
}

因為赐纱，要查找的變量 x 可能出現(xiàn)在數(shù)組的任意位置。如果數(shù)組中第一個元素正好是要查找的變量 x熬北，那就不需要繼續(xù)遍歷剩下的 n-1 個數(shù)據(jù)了疙描，那時間復(fù)雜度就是 O(1)。
但如果數(shù)組中不存在變量 x讶隐，那我們就需要把整個數(shù)組都遍歷一遍起胰，時間復(fù)雜度就成了 O(n)。不同的情況下巫延，這段代碼的時間復(fù)雜度是不一樣的效五。
最好情況時間復(fù)雜度（best case time complexity）

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

最壞情況時間復(fù)雜度 (worst case time complexity)

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

平均情況時間復(fù)雜度 (average case time complexity)

概率論的方法求加權(quán)平均值疼阔，即每種情況發(fā)生的次數(shù) x 每種情況發(fā)生的概率 之和戒劫。

網(wǎng)站導(dǎo)航

網(wǎng)站導(dǎo)航