# 複雜度分析 ###### tags: `競程`、`簡報` --- ## 好的演算法？ - 跑的多快 - 佔用的記憶體 - 正確性 --- 我們通常在乎“跑的多快” --- 那要怎麼知道速度呢？ 直接寫出來測量！ --- 但是直接測量有不少缺點： - 如果要跑很久才能結束 - 必須先寫出來才 - 不同電腦的跑 - 不同的輸入 - 不同的數據大小 --- ## 複雜度分析 以數學方法可以預估程式跑得多快 --- 首先我們先來看些例子： 假設加法會花掉 $c_1$ 的時間，比較會花掉 $c_2$ 的時間 ```cpp= for (int i=0,res=1; i<n; i++) { res = max(res, a[i]); } ``` for 迴圈用掉了 $n$ 次加法 迴圈內用了 $n$ 次比較 記 $f_1(n) = n(c_1+c_2)$ --- 假設加法會花掉 $c_1$ 的時間，乘法會花掉 $c_3$ 的時間 ```cpp= for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { res = res + i*j; } } ``` for 迴圈用了 $n^2$ 加法 迴圈內用了 $n^2$ 次加法和 $n^2$ 次乘法 記 $f_2(n) = n^2(2c_1+c_3)$ --- ### 複雜度分析的概念 $f_1(n) = n(c_1+c_2)$ $f_2(n) = n^2(2c_1+c_3)$ 哪個更快？ 這取決於 $c_1, c_2, c_3$ --- ### 複雜度分析的概念 如果，$n$ 超級超級超級大呢？ --- ### 複雜度分析的概念 我們得到了一個結論： 我們只在乎成長速度 ---