- 前言
- 為什麼需要複雜度分析
- 大O複雜度表示法
- 如何進行複雜度分析
- 幾種常見時間複雜度
- 空間複雜度
文章是觀看王争老師的資料結構與算法之美所寫
前言
資料結構和算法本身是為了解決快和省的問題，我們希望代碼運作快，并且希望節省存儲空間，是以執行效率是一個很重要的考量名額，接下來要講的是時間複雜度和空間複雜度
為什麼需要複雜度分析
我們可以通過把代碼跑一遍，然後通過統計，監控等得到算法執行事件和占用的記憶體空間大小，這種方法是事後統計法，有很大的局限性:
- 測試結果很依賴測試環境
- 同樣的代碼在不同的機器執行速度可能不一樣
- 測試結果受資料規模的影響很大
- 比如排序
是以，我們需要用一個不需要具體的測試資料來測試，就可以粗略地估計算法的執行效率的方法，也就是時間，空間複雜度分析方法。
大O複雜度表示法
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
} 假設每行代碼執行的時間都是一樣，為unit_time時間，那麼總的執行時間就是(2n+2)unit_time,所有代碼的執行時間T(n)和每行代碼的執行次數f(n)成正比。
我們可以把這個規律總結成一個公式。注意，大 O 就要登場了！
- T(n)表示代碼的執行時間，n表示資料規模大小
- f(n)表示每行代碼執行的次數總和
- O表示代碼的執行時間T(n)和f(n)成正比
- 上面所說的例子T(n)=O(2n+2),這就是大O時間複雜度表示法
- 大 O 時間複雜度實際上并不具體表示代碼真正的執行時間，而是表示代碼執行時間随資料規模增長的變化趨勢，是以，也叫作漸進時間複雜度（asymptotic time complexity），簡稱時間複雜度。
如何進行複雜度分析
- 隻關注循環執行次數最多的一段代碼
- 加法法則：總複雜度等于量級最大的那段代碼的複雜度
- 乘法法則：嵌套代碼的複雜度等于嵌套内外代碼複雜度的乘積
幾種常見時間複雜度
- 隻要代碼的執行時間不随 n 的增大而增長，這樣代碼的時間複雜度我們都記作 O(1)。