--- ###### tags: `2021 師大附中資訊科暑期培訓` --- # 時間複雜度 2021 師大附中資訊科暑期培訓 joylintp --- ## 為什麼會 TLE？ * 運算次數過多 ---- 大部分電腦每秒可執行約 10⁸ 到 10⁹ 次基本運算 ---- ```cpp= int ans = arr[0]; for (int i = 0; i < n; i++) ans = max(ans, a[i]); ``` 以上程式碼進行幾次運算？ ---- * `int ans = arr[0]`：1 次 * `int i = 0`：1 次 * `i < n`：`n` + 1 次 * `i++`：`n` 次 * `ans = max(ans, a[i]);`：`n` 次 ---- 對於每個指令計算個別執行的次數過於複雜， 在演算法競賽中通常使用 **時間複雜度** 估計執行次數 --- ## 時間複雜度 ---- ### 區間最大連續和 給一個長度為 $N$ 的數列 $A_i\ (|A_i| \le 10^9)$， 求連續的一段整數總和最大可以是多少 Input: ``` 5 3 -1 3 -5 4 ``` Output: ``` 5 ``` ---- ```cpp= int ans = 0; for (int i = 1; i <= N; i++) for (int j = i; j <= N; j++) { int tmp = 0; for (int k = i; k <= j; k++) tmp += A[k]; ans = max(ans, tmp); } ``` → $O(N^3)$ → $N \le 400$ 時可在 1 秒內執行完 ---- ```cpp= int pre[N + 1]; pre[0] = 0; for (int i = 1; i <= N; i++) pre[i] = pre[i - 1] + A[i]; int ans = 0; for (int i = 1; i <= N; i++) for (int j = i; j <= N; j++) ans = max(ans, pre[j] - pre[i - 1]); ``` → $O(N^2)$ → $N \le 8000$ 時可在 1 秒內執行完 ---- ```cpp= int ans = 0, now = 0; for (int i = 1; i <= N; i++) { now = max(0, now + A[i]); ans = max(ans, now); } ``` → $O(N)$ → $N \le 5 \times 10^6$ 時可在 1 秒內執行完 --- ### 更多時間複雜度判斷練習 $f(n) + g(n) = O(max(f(n), g(n))$ $f(n)g(n) = O(f(n)g(n))$ ---- ```cpp= bool isprime = true; for (int i = 2; i * i <= n; i++) if (n % i == 0) { isprime = false; break; } ``` → $O(\sqrt{n})$ ---- ```cpp= vector<int> bin; while (n) bin.push_back(n % 2), n /= 2; reverse(bin.begin(), bin.end()); ``` → $O(\log{n})$ ---- ```cpp= int c = a + b; int d = a * c; ``` → $O(1)$ ---- ```cpp= for (int i = 0; i < n; i++) { while (i < n && arr[i] < k) i++; v.push_back(i); } ``` → $O(n)$ ---- ```cpp= priority_queue<int> pq; for (int i = 0; i < n; i++) pq.push(arr[i]); ``` → $O(n\log{n})$ → 並非所有操作都是常數時間（$O(1)$）內完成 ---- ```cpp= int gcd(int a, int b) { if (a == 0) return b; else return gcd(b % a, a); } ``` → $O(\log{max(a, b)})$ → 計算遞迴的時間複雜度較困難