什么是復雜度分析?
- 數(shù)據(jù)結構和算法解決的是如何讓計算機
更快卖词、更省空間的執(zhí)行。 - 因此需要從兩個方面評估數(shù)據(jù)結構和算法的優(yōu)越性吏夯。
- 分別用時間復雜度和空間復雜度兩個概念來描述性能問題,二者統(tǒng)稱為復雜度此蜈。
- 復雜度描述的是算法的執(zhí)行時間或者占用空間的大小與數(shù)據(jù)規(guī)模增長關系。
為什么需要復雜度分析?
- 和性能測試相比,復雜度分析有不依賴執(zhí)行環(huán)境裆赵、成本低、效率高跺嗽、易操作战授、指導性強。
- 掌握復雜度分析桨嫁，將能編寫出性能更優(yōu)的代碼植兰，有利于降低系統(tǒng)開發(fā)和維護成本。
如何進入復雜度分析璃吧？
大O表示法：就是在不用運行代碼的情況下楣导，用“肉眼” 得出一段代碼的執(zhí)行時間。
- 來源：算法的執(zhí)行時間與每行代碼的執(zhí)行次數(shù)成正比肚逸，用 T(n) = O(f(n)) 表示爷辙，其中 T(n) 表示算法執(zhí)行總時間，f(n) 表示代碼執(zhí)行總次數(shù)朦促，而 n 往往表示數(shù)據(jù)的規(guī)模膝晾。
- 特點：以時間復雜度為例，由于時間復雜度描述的是算法執(zhí)行時間與數(shù)據(jù)規(guī)模的增長變化趨勢务冕，所以“常量階”血当、低階、系數(shù)實際上對這種趨勢不產(chǎn)生決定性影響禀忆，所以在做時間復雜度分析時可以忽略這些項臊旭；只需要記錄一個最大量級就可以了。
- 大O 時間復雜度并不是實際代碼真正的運行時間箩退，而是表示代碼執(zhí)行時間歲數(shù)據(jù)規(guī)模增長的變化趨勢离熏；所以時間復雜度也叫
進時間復雜度。
總結：所有代碼的執(zhí)行時間 T(n) 與每行代碼的執(zhí)行次數(shù)n成正比; 總結公式: T(n) = O(f(n))
時間復雜度分析
- 只關注
循環(huán)次數(shù)最多的一段代碼戴涝。 - 加法法則：總復雜度等于
量級最大的那段代碼的復雜度; 總結公式: 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))) - 乘法法則: 嵌套代碼的復雜度等于嵌套內(nèi)外代碼復雜度的乘積; 總結公式: T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)*g(n))
- 多規(guī)模求加法: 比如方法有兩個參數(shù)控制兩個循環(huán)的次數(shù)，那么這時就取二者復雜度相加奸鸯。
復雜度量級（按數(shù)量級遞增）
-
多項式階
- 常量階 O(1)
- 對數(shù)階 O(logn)
- 線性階 O(n)
- 線性對數(shù)階 O(nlogn)
- 平方階 O(n2)咪笑、立方階 O(n3) ... k 次階 O(nk)
-
非多項式
- 指數(shù)階 O(2n)
- 階乘階 O(n!)
復雜度量級
空間復雜度分析
空間和復雜度和時間復雜度分析方法基本類似，表示算法的存儲空間與數(shù)據(jù)規(guī)模之間的增長關系娄涩。
