# 競程與時間複雜度
---
## 網路免費學習資源
* [2014 資訊之芽算法班影片](https://www.youtube.com/watch?v=_r7cfVrn28c)
* 完全不知道時間複雜度的人請先看此影片
* 我們課程只做簡單複習及講解更深的內容
* [2021 資訊之芽投影片](https://www.csie.ntu.edu.tw/~sprout/algo2021/ppt_pdf/week02/complexity_inclass.pdf)
---
## 計算演算法的時間複雜度的常見方法
----
### 一、數迴圈
* 請計算以下程式碼的時間複雜度
```cpp=
#include<iostream>
using namespace std;
int main() {
int A, B, cnt = 0;
cin >> A >> B;
for(int i = 0; i < A; i++) {
for(int j = 0; j < B; j++) {
for(int k = 0; k < B; k++) {
cnt++;
}
}
for(int j = 0; j < A; j++) {
cnt++;
}
}
for(int i = 0; i < B; i++) {
for(int j = 0; j < A; j++) {
cnt++;
}
}
cout << cnt << '\n';
return 0;
}
```
----
### 二、數學分析
* 示範例題：[ARC113 A - A\*B\*C](https://atcoder.jp/contests/arc113/tasks/arc113_a)
* 題意：給定 $K$ ($K \le 2 \times 10^5$)，有多少組 $(A,B,C)$ 滿足 $A, B, C$ 都是正整數且 $A \times B \times C \le K$ ?
----
* $O(K^3)$ 的解法：
```cpp=
#include<iostream>
using namespace std;
void solve() {
int K;
cin >> K;
long long an = 0;
for(int A = 1; A <= K; A++) {
for(int B = 1; B <= K; B++) {
for(int C = 1; C <= K; C++) {
if(A * 1LL * B * C <= K) an++;
}
}
}
cout << an << endl;
}
int main() {
solve();
return 0;
}
```
----
* $O(K^2)$ 的解法：
```cpp=
#include<iostream>
using namespace std;
void solve() {
int K;
cin >> K;
long long an = 0;
for(int A = 1; A <= K; A++) {
for(int B = 1; B <= K; B++) {
an += K / (A * 1LL * B);
}
}
cout << an << endl;
}
int main() {
solve();
return 0;
}
```
----
* 請計算以下解法的時間複雜度：
```cpp=
#include<iostream>
using namespace std;
void solve() {
int K;
cin >> K;
long long an = 0;
for(int A = 1; A <= K; A++) {
for(int B = 1; A * B <= K; B++) {
an += K / (A * 1LL * B);
}
}
cout << an << endl;
}
int main() {
solve();
return 0;
}
```
----
* 實際上，這題是有辦法做到 $O(K^{2/3})$ 而且方法也很簡單，只是數學分析比較困難。
* 有興趣者請參考 [ABC 227 C - ABC conjecture](https://atcoder.jp/contests/abc227/tasks/abc227_c) 的題解尋求靈感。
----
### 時間複雜度計算練習題
----
* 練習題一：請問以下程式碼的時間複雜度是？
```cpp=
cin >> n;
while(n > 0){
for(int i = 0; i < n; i++) {
// O(1) operations
}
n /= 2;
}
```
----
* 練習題二：請問以下程式碼的時間複雜度是？
```cpp=
long long n;
cin >> n;
while(n > 1){
// O(1) operations
n = (int)sqrt(n);
}
```
----
* 練習題三：請問以下程式碼的時間複雜度是？
```cpp=
cin >> n;
for(int i = 0; i < (1 << n); i++) {
for(int j = i; j ; j = (j - 1) & i) {
// O(1) operations
}
}
```
----
### 三、均攤分析
* 這部分我們後面再說 :innocent:
---
## 時間複雜度計算的常見陷阱
----
### 常見陷阱 1
* 並不是每個函數的執行時間都是 O(1)
* 在使用現成函式時請搞清楚他的時間複雜度
* 例如 strlen()、vector 的 insert() 和 erase() 等是眾多新手最常誤用的東西
----
* 問題：給一個由小寫字母組成的字串，長度不超過 $10^6$，請問至多能從此字串選多少組不重疊的長度為 2 的子字串，使得每個選上的子字串都是由兩個一樣的字母組成？
* 例如，``aabbbabaa`` 中，我們可以選三組如下：
* [aa][bb]bab[aa]
----
* 會 TLE 的程式碼
```cpp
#include<cstring>
#include<cstdio>
#include<cstdlib>
const int SIZE = 300010;
char s[SIZE];
int main() {
// scanf("%s", s);
int n = SIZE - 10;
for(int i = 0; i < n; i++) s[i] = 'a' + rand() % 2;
int an = 0;
for(int i = 1; i < strlen(s); i++) {
if(s[i] == s[i - 1]) {
s[i] = '@';
an++;
}
}
printf("%d\n", an);
return 0;
}
```
----
* 再以 [APCS-2016 P3 定時K彈](https://zerojudge.tw/ShowProblem?problemid=c296) 為例：
```cpp=
// 程式碼來源：https://sites.google.com/site/zsgititit/zi-xun-neng-li-jian-ding/apcs/10510di3ti-ding-shik-dan
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m, k, now;
vector<int> p;
// int n = 200000, m = 1, k = 199999; // 會 TLE 的測試資料
while (cin >> n >> m >> k) {
p.clear();
for (int i = 1; i <= n; i++) {
p.push_back(i);
}
now = 0;
for (int i = 0; i<k; i++) {
now = (now + m - 1) % p.size();
p.erase(p.begin() + now);//刪除被炸的人
}
now = now % p.size();
cout << p[now]<<endl;
}
}
```
----
* 當 n = 200000, m = 1, k = 199999 就會 TLE 了。
* 拿 「APCS 定時K彈」當關鍵字搜出來參考作法有不少都是 $O(n^2)$ 的作法。
* 若想要知道不會 TLE 的作法可參考 [許爸與小捲毛的 Youtube 解說](https://www.youtube.com/watch?v=iNVbJSp0aUI)
----
### 常見陷阱 2
* 拿並非基本資料型態的物件作運算時，時間複雜度不一定是 O(1)，大家可以拿以下程式碼實驗看看：
```cpp=
#include<iostream>
#include<string>
using namespace std;
const int SIZE = 250010;
int main() {
string s;
for(int i = 0; i < SIZE; i++) {
s = s + 'a';
}
cout << s << '\n';
return 0;
}
```
----
### 常見陷阱 3
* 在函數傳遞一個記憶體使用量很大的物件時，相當於把整個物件複製一份，所以並不是 O(1)，大家可以拿以下程式碼實驗看看：
```cpp=
#include<iostream>
#include<string>
using namespace std;
const int SIZE = 300010;
int f(string s, int x) {
return (int)s[x];
}
int main() {
string s(SIZE, 'a');
int an = 0;
for(int i = 0; i < SIZE; i++) {
an+=f(s, i);
}
cout << an << '\n';
return 0;
}
```
---
## 如何測試自己程式碼在 OJ 上的效率？
----
* 示範例題：[O(n) 極限測試題 1：級數求和](https://codeforces.com/group/m7tZBvb5sH/contest/369768/problem/A)
----
* 假設我只會 O(n) 暴力，這樣也能 AC 嗎 !?
```cpp=
#include<iostream>
using namespace std;
void solve() {
unsigned long long l, r, answer = 0;
cin >> l >> r;
for(auto i = l; i <= r; i++) answer += i;
cout << answer << '\n';
}
int main() {
solve();
return 0;
}
```
----
* 同個程式碼在每個 OJ 上的執行時間都不一樣
* 如何在各大 OJ 測試執行時間？
----
* 比較常辦競賽的 OJ 中，幾乎都存在一個頁面可以讓你測程式碼速度和執行結果
* 若沒有這樣的頁面，就只能找一個時限比較長的舊題來測了。
---
## 常數在競程中的重要性
----
* 競程中答對題目標準並不是使用人工批改，所以並無法保證用比較好的時間複雜度的演算法就能 AC，也不一定能避免一些時間複雜度比較差但常數很小的作法 AC。
* 所以我們 AA 競程的課程非常注重每個演算法要怎麼實作常數才會比較小。
----
### 1. 程式語言、編譯環境的選擇
* 用前面展示過的 [O(n) 極限測試題 1：級數求和](https://codeforces.com/group/m7tZBvb5sH/contest/369768/problem/A) 的程式碼為例，換個編譯器版本，竟然就快了兩倍。
* [Codeforces Clang++ 17 Diagnostics 的官方說明](https://codeforces.com/blog/entry/55902)
* [Codeforces C++ 64 bit 的官方說明](https://codeforces.com/blog/entry/75004)
----
### 2. 編譯參數、硬體加速
----
#### OJ 上編譯參數的說明
* 一個比較有規模的比賽或競賽網站，都應該存在某個頁面介紹該比賽或平台使用的各個語言的編譯選項
* [Codeforces 的頁面](https://codeforces.com/blog/entry/4088)
* [Atcoder 的頁面](https://atcoder.jp/contests/abc242/rules)
----
#### 參數 O2 的介紹
* 加了 O2 這個參數，可以讓編譯器幫你優化程式碼的邏輯，也就是改進你演算法執行時間的常數，甚至連時間複雜度都有機會被優化。
* 可查看組與的網站：[godbolt.org](https://godbolt.org/)
* [供大家實驗 O2 的性能程式碼](https://gist.github.com/dreamoon4/3582aacabac109b0db47c9cd49140970)
* [編譯器各種優化選項的介紹](https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html)
----
#### 更多可拿來實驗 O2 的作用的程式碼
* [被優化掉的空回圈](https://gist.github.com/dreamoon4/eeaef91376c51055ba1763bc8b950cb1)
* [等差級數測試](https://gist.github.com/dreamoon4/f74528b7ce4f5cdb884e38435330c98b)
----
#### 編譯優化和硬體優化
* [Codeforces 上的編譯優化及硬體優化教學](https://codeforces.com/blog/entry/96344)
----
能見證硬體優化的奇蹟的題：
* [CF851 A. Arpa and a research in Mexican wave](https://codeforces.com/contest/851/problem/A)
* [CF449 E. Welcome home, Chtholly](https://codeforces.com/contest/896/problem/E)
* 可用這兩題見證硬體優化的威力。
----
### 3. 使用的操作類型
* 電腦執行不同類型的操作所需時間都不同。
* [參考資料](http://ithare.com/infographics-operation-costs-in-cpu-clock-cycles/)
* 我們在設計方法時，除了考慮到操作次數外，也要考慮到操作類型，一個常見的例子就是除法、取餘的運算非常慢，若有其他方法取代的話，就不要使用除法和取餘。
* 以 [2 的幂](https://codeforces.com/group/m7tZBvb5sH/contest/369768/problem/B) 這題為例，我們可以發現取餘運算比 (if 判斷式) + (減等於運算) 還慢。
----
### 4. I/O 處理方式
* [WiwiHo 競程筆記裡的 I/O 優化介紹](https://cp.wiwiho.me/io-optimize/)
* [I/O 優化的實驗紀錄](https://docs.google.com/spreadsheets/d/1HPWVV5Tk43jMPdzXtGEkfbnR8bY6JOhx0JF0iKjvc5k/edit?usp=sharing)
----
* 使用 cin 時的注意事項：
1. 讀入的量很大時，請記得在所有讀入之前加上：
```cpp
cin.tie(0);ios_base::sync_with_stdio(false);
```
2. 請使用 '\n' 取代 std::endl。
3. 若有使用 1. 中的程式碼，不可以將 cin/cout, scanf/printf 混用。
----
* 使用 cin 時的注意事項：
4. 就算有使用 1. 中的程式碼，用 cin 讀入浮點數仍會很慢，需使用 scanf。
5. 讀入的數字位數也會影響到輸入的時間。
* 在 Codeforces 上使用 scanf 時，選 64 bit 的編譯選項會特別慢。
----
### 進階 I/O 優化技巧
* 參考資料：oi-wiki 的 [读入、输出优化](https://oi-wiki.org/contest/io/)
* 關於讀入：
1. 把輸入全當成字元讀入後再自己轉換成整數型態會更快。
2. 使用 fread() 又會更快。
* 關於輸出：
1. 輸出字串會比數字一個一個輸出還快。
2. 在 C++17 以後，使用 to_chars 把數字(浮點數也可以)轉成字串會特別快。
----
### 5. Memory Cache
* [一個介紹 Memory Cache 的 Blog](http://opass.logdown.com/posts/249025-discussion-on-memory-cache)
* [一個關於 Cache 的實驗](https://codeforces.com/blog/entry/69685)
----
* 再以 [矩陣相乘](https://codeforces.com/group/m7tZBvb5sH/contest/369768/problem/H) 這題為例
* for 迴圈枚舉的變數由外到內依序是 i, j, k
* [使用 mul[i][j]+=a[i][k]\*b[k][j]](https://codeforces.com/group/m7tZBvb5sH/contest/369768/submission/154246107) : 2106 ms
* [使用 mul[i][k]+=a[i][j]\*b[j][k]](https://codeforces.com/group/m7tZBvb5sH/contest/369768/submission/154246130) : 1419 ms
* [使用 mul[k][i]+=a[k][j]\*b[j][i]](https://codeforces.com/group/m7tZBvb5sH/contest/369768/submission/154246169) : 4851 ms
---
# 出題者是如何決定時限的
----
* 分三種類型的題目討論
1. 簡單的實作題
2. 著重在思維的題
3. 要求做題者使用某種時間複雜度的題
----
* 簡單的實作題
* 目的是測驗做題者能否實做出正確的程式碼，不在乎使用的方法的時間複雜度。
* 通常時限會給的很寬鬆。
* 多數線上賽的簡單題以及 APCS 前兩題都是屬於這一類。
----
* 著重在思維的題
* 目的是測試做題者是否能設計出時間複雜度比暴力的方法還好的演算法。
* 這樣的題目在設計測試資料範圍和時限，通常只考慮不能讓暴力的方法通過。例如，若做題者的時間複雜度比標程多個 $\log n$ 也是能通過。
----
* 要求做題者使用某種時間複雜度的題
* 出題者會期望做題者一定要做到和標程一樣的時間複雜度才能答對
* 因此時限會給的很緊
----
* 通常越難的題，時間限制會越緊，因為出題者都深怕參賽者使用比較糟的時間複雜度加上一些優化常數方法通過，以失公平性(~~更可能是自己出的題被爛方法過會不開心所致~~)，所以有不少難題都不存在以些比較慢的程式語言(如 Python) 能通過的程式碼。
----
* 每個 OJ 或比賽都會有自己關於執行時間限制的規範，舉例來說：
* Codeforces：至少是 java 參考程式碼執行時間的 2 倍以上
* 台灣 ICPC：至少是 java 參考程式碼執行時間的 2 倍以上或是 C++ 參考程式碼的 5 倍以上
----
* 看到這裡，相信大家就能感受出我們前面所講的這些會影響執行時間常數 $2$ 倍以上的各項因素有多重要了。
----
額外補充：
1. 一般而言比賽主辦方會禁止出題者在標程內使用一些特殊的優化方式如 I/O 優化或是硬體優化。
2. （~~規範就是用來打破用的~~）這些規範也只是建議，若出題者認為有必要，還是會設置更緊的時間限制，如：2022 Codechef SnackDown Elimination([相關評論](https://codeforces.com/blog/entry/97516?#comment-864936))
3. Atcoder 這個 OJ 對做題者特別友好，時間限制都設置的很寬鬆，所以對於做題者來說，比其他 OJ 更容易使用時間複雜度比出題者更差的方法 AC。
---
# 附錄：隨機測試資料的弊病
----
* 出題者該如何產生測試資料是個需要討論很久的課題，其中大家最常用的方法就是每個輸入的變數都使用程式語言的內建隨機函數(如 [C++ 的 rand()](https://en.cppreference.com/w/cpp/numeric/random/rand))來產生所有可能數值。
* 但若測試資料總是使用這樣的方式產生，會對比賽的公正性造成影響...
----
* 先以 [ICPC 2021 台灣站 B 題](https://drive.google.com/file/d/1YUMxajkblszqjcVhb3ksvv1UL44JOlJT/view)為例(可在 [Codeforces Gym](https://codeforces.com/gym/103443/problem/B) 上傳測試)
* 暴力的 $O(N^3)$ 做法：[程式碼](https://gist.github.com/dreamoon4/28e3cb62ec0c1fdf571835901e26d7a6)
* 此程式碼花了 2620 ms 通過此題
----
* 此題執行時間的瓶頸是 $s1$ 和 $s2$ 兩個字串相同位置的字元是否相等的比較次數
* 假設此題測試資料是用[此程式碼](https://gist.github.com/dreamoon4/9efdf44c2d0e1966ef7c619fbdc792ea)產生，請計算比較次數的期望值
* [期望值的介紹](http://www.math.nsysu.edu.tw/eprob/ProbConcept/expectation/index.html)
----
* 答案是：6270852087.5
* 約等於 $6.2 \times 10^9$
* 和理論的最大值 $2.5 \times 10^{10}$ 差了 4 倍
* 若測試資料裡 $n$ 的值是隨機生的，$3$ 秒能通過也還算合情合理了。
----
* 很多人都會直覺的認為測試資料若是隨機生成的，對於執行時間的常數只會有兩倍左右的影響，但其實還是要依題目而定，老師甚至有見過差到 9 倍的。
* 請嘗試計算看看公開課題單的 [F 題](https://codeforces.com/group/m7tZBvb5sH/contest/369768/problem/F) 和 [G 題](https://codeforces.com/group/m7tZBvb5sH/contest/369768/problem/G) 常數會差多少呢？
----
### 練習題
* 公開課題單 [F 題](https://codeforces.com/group/m7tZBvb5sH/contest/369768/problem/F) 和 [G 題](https://codeforces.com/group/m7tZBvb5sH/contest/369768/problem/G) 只差在測試資料的產生方式
* 給定此[暴力做法](https://gist.github.com/dreamoon4/b5a7da548c6b942d43c00d3614637d14)，請嘗試計算
1. F 題中 an += a[x++]; 這行執行次數的期望值
2. 在 G 題中，an += a[x++]; 執行次數至多是多少？
{"metaMigratedAt":"2023-06-16T19:44:12.542Z","metaMigratedFrom":"YAML","title":"競程與時間複雜度","breaks":true,"slideOptions":"{\"transition\":\"fade\",\"parallaxBackgroundImage\":\"https://i.imgur.com/jtMhsLP.png\",\"parallaxBackgroundHorizontal\":200,\"parallaxBackgroundVertical\":200}","contributors":"[{\"id\":\"ec58fb73-fce8-4e38-b318-d00e84653449\",\"add\":16657,\"del\":5196}]"}