# 複雜度 by : hush --- 如何判斷一個程式碼的效率呢? ---- 看它的執行的時間和使用的記憶體量多寡 也就是**時間複雜度**和**空間複雜度** --- ## 時間複雜度 ---- 我們先當作所有簡單運算的執行時間都一樣 * 加減乘除： $a+b$ * 取餘數： $a\% b$ * 位元運算： $a|b$ * 存取記憶體： $a[i]$ * 判斷運算子： $a\lt b$ * 賦值運算子： $a = b$ ---- 然後算出程式一共要執行幾次簡單運算 ---- 例如： ```cpp= int n; cin >> n; for (int i=0;i<n;i++) cout << "Hello World\n"; ``` ```cpp=3 //執行次數：n+2 ``` ```cpp= int n; cin >> n; for (int i=0;i<n;i++) { for (int i=0;i<n;i++) { cout << i << " : Hello World\n"; } } for (int i=n-1;i>=0;i--) cout << "Hello World\n"; ``` ```cpp=10 //執行次數：2n²+n+2 ``` ---- 但每次都要列出式子很麻煩 其實只要看影響最大的項就好了 這時就可以使用**Big-O**符號 ---- 可以忽略影響不大的首項係數和低次項，例如： * $3𝑛^3 + 5𝑛^2 + 10𝑛 + 3 = O(n^3)$ * $\tfrac{1}{10}𝑛^5 + 50𝑛^4 - 100𝑛 = O(n^5)$ * $888 = O(1)$ ---- 換你們了： * $7𝑛^2 + 5𝑛 -1000 = O(???)$ * ||$O(n^2)$|| * $2^n + n^3 = O(???)$ * ||$O(2^n)$|| * $\sum\limits_{k = 1}^n{\tfrac{n}{k}} = \tfrac{n}{1} + \tfrac{n}{2} + \dots + \tfrac{n}{n} = O(???)$ * ||$O(n\cdot ln(n)), ln=log_e$|| ---- 這些呢？ ```cpp= for (int i=0;i<n;i++) for (int j=i-1;j>=0;j--) cout << '*' << " \n"[j==0]; ``` ||$O(n^2)$|| ```cpp= sort(a,a+n); ``` ||$O(nlogn)$|| ---- ```c= int f(int i) { if (i<2) return i; return f(i-1)+f(i-2); } main() { //it's C language int n,m; scanf("%d %d",&n,&m); printf("%d\n",f(n)-f(m)); } ``` ||$O(\phi ^n)\approx O(2^n)$|| --- ## 空間複雜度 ---- 跟時間複雜度類似 算出程式一共要開幾個空間 ---- 一樣也會用Big-O符號來表示複雜度 ---- 例如： ```cpp= int a[n]; //空間複雜度O(n) int a[n][m]; //空間複雜度O(n*m) long long a,b,c,d,e; //空間複雜度O(1) ``` --- ## 使用方法 ---- 先講**時間複雜度** ---- 一般的OJ一秒約可以跑$10^8$個簡單運算！ 把數字帶入複雜度估算程式會不會超時 (寫久了會用數字推算複雜度) ---- 例如： * 複雜度是$O(n^2)$，題目說：$n\le 10^5$ $10^{5^2}=10^{10}\gt 10^8\implies$ TLE * 複雜度是$O(n^3)$，題目說：$n\le 10^2$ $10^{2^3}=10^{6}\lt 10^8\implies$ AC ---- 數字範圍與複雜度對應表 (多寫題目就記起來了)  ---- 接下來是**空間複雜度** ---- 基本上你陣列不開到超過$2\times 10^7$都會過 除了一些很搞的題目以外空間不太需要在意 ---- 因為電腦記憶體配置的[某些原因](https://sprout.tw/algo2024/homework/hand03.pdf) 陣列要開全域變數，不然有可能會報錯 ```cpp= #include<iostream> #define int long long #define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0); using namespace std; int a[100000]; signed main() { //colinorz; } ``` --- ## 總結 ---- 複雜度是解題最基本、最重要的部分 每一題都**必須**先算過複雜度再寫 ---- 所以請不要盲目地看到題目就開始寫 請先算過你寫出來的程式碼會過再寫 --- # 謝謝大家