什么是復(fù)雜度分析?

1. 數(shù)據(jù)結(jié)構(gòu)和算法解決的是如何讓計(jì)算機(jī) 更快、更省空間的執(zhí)行。
2. 因此需要從兩個(gè)方面評估數(shù)據(jù)結(jié)構(gòu)和算法的優(yōu)越性。
3. 分別用時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)概念來描述性能問題,二者統(tǒng)稱為復(fù)雜度。
4. 復(fù)雜度描述的是算法的執(zhí)行時(shí)間或者占用空間的大小與數(shù)據(jù)規(guī)模增長關(guān)系。

為什么需要復(fù)雜度分析?

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

如何進(jìn)入復(fù)雜度分析？

大O表示法：就是在不用運(yùn)行代碼的情況下，用“肉眼” 得出一段代碼的執(zhí)行時(shí)間。

1. 來源：算法的執(zhí)行時(shí)間與每行代碼的執(zhí)行次數(shù)成正比，用 T(n) = O(f(n)) 表示，其中 T(n) 表示算法執(zhí)行總時(shí)間，f(n) 表示代碼執(zhí)行總次數(shù)，而 n 往往表示數(shù)據(jù)的規(guī)模。
2. 特點(diǎn)：以時(shí)間復(fù)雜度為例，由于時(shí)間復(fù)雜度描述的是算法執(zhí)行時(shí)間與數(shù)據(jù)規(guī)模的增長變化趨勢，所以“常量階”、低階、系數(shù)實(shí)際上對這種趨勢不產(chǎn)生決定性影響，所以在做時(shí)間復(fù)雜度分析時(shí)可以忽略這些項(xiàng)；只需要記錄一個(gè)最大量級就可以了。
3. 大O 時(shí)間復(fù)雜度并不是實(shí)際代碼真正的運(yùn)行時(shí)間，而是表示代碼執(zhí)行時(shí)間歲數(shù)據(jù)規(guī)模增長的變化趨勢；所以時(shí)間復(fù)雜度也叫 進(jìn)時(shí)間復(fù)雜度。

總結(jié)：所有代碼的執(zhí)行時(shí)間 T(n) 與每行代碼的執(zhí)行次數(shù)n成正比; 總結(jié)公式: T(n) = O(f(n))

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

1. 只關(guān)注循環(huán)次數(shù)最多的一段代碼。
2. 加法法則：總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度; 總結(jié)公式: T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))
3. 乘法法則: 嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積; 總結(jié)公式: T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)*g(n))
4. 多規(guī)模求加法: 比如方法有兩個(gè)參數(shù)控制兩個(gè)循環(huán)的次數(shù)，那么這時(shí)就取二者復(fù)雜度相加。

復(fù)雜度量級（按數(shù)量級遞增）

• 多項(xiàng)式階

  • 常量階 O(1)
  • 對數(shù)階 O(logn)
  • 線性階 O(n)
  • 線性對數(shù)階 O(nlogn)
  • 平方階 O(n2)、立方階 O(n3) ... k 次階 O(nk)

• 非多項(xiàng)式

  • 指數(shù)階 O(2n)
  • 階乘階 O(n!)

復(fù)雜度量級

空間復(fù)雜度分析

空間和復(fù)雜度和時(shí)間復(fù)雜度分析方法基本類似，表示算法的存儲(chǔ)空間與數(shù)據(jù)規(guī)模之間的增長關(guān)系。