Complexity - HackMD

# Complexity 複雜度社課講義p.41~p.43 by Colin ---- ## What is complexity? - complexity n. 複雜(度) - Time Complexity 時間複雜度 - 評估程式執行時間 - 時間複雜度越大=>執行時間越久 - Space Complexity 空間複雜度 - 評估程式使用空間 - 空間複雜度越大=>使用記憶體越多 --- ## Time Complexity 時間複雜度 - 描述演算法的執⾏時間與輸入資料個數$n$之間的關係 ---- ## Big-O符號：O() - 複雜度透過Big-O符號表⽰函數接近極限的⾏為 - （通常不包括這個函數的低階項和⾸項係數） - Big-O：$f(x)=O(g(x))$ 表⽰$g(x)$的成⻑趨勢⼤於等於$f(x)$ ---- Example 1 ```cpp= cout<<"Hello, world\n"; ``` 程式執行次數：$1$ 時間複雜度：$O(1)$ ---- Example 2 ```cpp= int n; cin>>n; for(int i=0;i<n;i++){ cout<<"Hello, world\n"; } ``` 程式執行次數：$n$ 時間複雜度：$O(n)$ ---- Example 3 ```cpp= int n; cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cout<<"Hello, world\n"; } } ``` 程式執行次數：$n^2$ 時間複雜度：$O(n^2)$ ---- ## Big-O符號表⽰通常會省略影響不大的低階項和⾸項係數 ex: 程式執行次數：$2n^5+7n^3+10n+12345$ 時間複雜度：$O(n^5)$ 程式執行次數：$\sqrt{n}+10+7n$ 時間複雜度：$O(n)$ 程式執行次數：$2n\times 3n^2\times 5n^3$ 時間複雜度：$O(n^6)$ ---- Example 4 ```cpp= int n; cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ cout<<"Hello, world\n"; } } ``` 程式執行次數：$0+1+2+...+(n-1)$=$\frac{n[0+(n-1)]}{2}$=$\frac{1}{2}n^2-\frac{1}{2}n$ 時間複雜度：$O(n^2)$ ---- ## 常見複雜度量值比較 $O(n^n)>O(n!)>O(2^n)>O(n^3)>O(n^2)$ $>O(nlogn)>O(n)>O(\sqrt{n})>O(logn)>O(1)$ 模擬：https://www.geogebra.org/calculator/rqmscpvz （只考慮$n>0$的情況） ---- ## 用時間複雜度估算程式執行時間 - 現今一般的Judge C/C++程式**一秒約可以執行$10^8$個簡單運算** - 可以用時間複雜度估算程式執行時間=>會不會TLE - 也可以用題目給的數值範圍和時間限制猜測要用什麼演算法 ---- **舉個例子：已知有一個題目給的參數為一正整數$n$，$1\le n\le 10^6$，題目時間限制為 $1$ 秒** 若使用時間複雜度$O(n^2)$的演算法，將極值$n=10^6$帶入$O(n^2)$，再除以$10^8$即為執行時間 $\Rightarrow$$\cfrac{(10^6)^2}{10^8}=10^4秒=2小時46分鐘40秒>1秒$，必TLE ---- **舉個例子：已知有一個題目給的參數為一正整數$n$，$1\le n\le 10^6$，題目時間限制為 $1$ 秒** 若使用時間複雜度$O(nlogn)$的演算法，將極值$n=10^6$帶入$O(nlogn)$，再除以$10^8$即為執行時間 $\Rightarrow$$\cfrac{10^6\cdot log_2(10^6)}{10^8}\approx 0.199秒<1秒$，符合時間限制 ---- **舉個例子：已知有一個題目給的參數為一正整數$n$，$1\le n\le 10^6$，題目時間限制為 $1$ 秒** 若使用時間複雜度$O(n)$的演算法，將極值$n=10^6$帶入$O(n)$，再除以$10^8$即為執行時間 $\Rightarrow$$\cfrac{10^6}{10^8}=0.01秒<1秒$，符合時間限制 ---- 以下數值範圍是假設題目時間限制為1秒 | 時間複雜度 | 例子 | 常見數值範圍 | | -------- | -------- | -------- | | $O(n!)$ | 窮舉所有排列 | $n\le 10$ | | $O(2^n)$ | 窮舉所有子集合 | $n\le 25$ | | $O(n^3)$ | 三層迴圈 | $n\le 500$ | | $O(n^2)$ | 雙迴圈、Bubble/Insertion/Selection Sort | $n\le 10^3$ | ---- | 時間複雜度 | 例子 | 常見數值範圍 | | -------- | -------- | -------- | | $O(nlogn)$ | Quick/Merge/Heap Sort | $n\le 10^5$ | | $O(n)$ | 單迴圈 | $n\le 10^6$ | | $O(\sqrt{n})$ | 求質數 | $n\le 10^{12}$ | | $O(logn)$ | 二分搜 | $n\le 10^{18}$ | | $O(1)$ | 一個簡單運算 | | --- ## Space Complexity 空間複雜度 - 描述演算法所需記憶體與輸入資料個數$n$之間的關係 ---- ## Big-O符號：O() - **以下計算方式跟時間複雜度相同!!!** - 複雜度透過Big-O符號表⽰函數接近極限的⾏為 - （通常不包括這個函數的低階項和⾸項係數） - Big-O：$f(x)=O(g(x))$ 表⽰$g(x)$的成⻑趨勢⼤於等於$f(x)$ ---- Example 1 ```cpp= int x=1; cout<<x<<'\n'; ``` 空間複雜度：$O(1)$ ---- Example 2 ```cpp= int n; cin>>n; int arr[n]; for(int i=0;i<n;i++){ cin>>arr[i]; } ``` 空間複雜度：$O(n)$ ---- Example 3 ```cpp= int n,m; cin>>n>>m; int arr[n][m]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>arr[i][j]; } } ``` 時間複雜度：$O(nm)$ ---- - 可以用空間複雜度計算程式使用記憶體大小 - 基本上現今電腦記憶體越來越⼤，其實已經不太需要在意空間複雜度了（除了⼀些很搞的題⽬可能會MLE，但幾乎不會遇到） ---- 補充：以空間換取時間的演算法 - 時間複雜度和空間複雜度是會相互影響的，許多高效的演算法都是以使用較大的記憶體空間換取較少的執行時間 - 例如：線段樹、DP(Dynamic Programming，動態規劃) ---- APCS觀念題 ![](https://hackmd.io/_uploads/Sybu48Bzp.png) --- Thank you for listening!