# 2024 Sprout C 語法班：STL 補充內容

## 淺談複雜度

在這個段落，我們將以「操作數」作為切入點，讓大家對複雜度有初步的了解。

在進入正題之前，我們可以先問問自己，為什麼需要學習「複雜度」的概念？

### 複雜度的重要性

學習複雜度的概念對於程式設計非常重要，因為沒有效率的程式常常會造成在解題時拿到 **TLE（Time Limit Exceeded）** 的評判結果。

在解決一個問題時，我們的程式需要在有限時間內完成執行。如果程式花費太多時間，超過問題的時間限制，則會被判定為 TLE，無法通過測試。

複雜度的概念能夠幫助我們**評估算法的效率**，並**預估算法在處理不同規模的測資的執行時間**。透過學習複雜度，我們可以了解到哪些算法更有效率，並且能夠選擇最適合的算法來解決問題。

如果我們使用一個時間複雜度較高的算法來解決問題，可能會導致執行時間過長，無法在給定的時間限制內完成。這意味著**即使我們的程式邏輯是正確的，但因為效率不足而無法獲得正確的結果**。

透過學習複雜度，我們能夠優化我們的程式，使其在處理較大規模測資時能夠更有效率地運行。

### 操作數

在程式設計中，「操作」是指對資料進行的各種處理或動作，例如讀取、寫入、計算等基礎運算。每一個操作都是程式中的一個指令或功能。

「操作數」則是指一個程式或算法所涉及的操作次數。一個程式將兩個數字相加，後再乘以五，其操作數就是 $2$。

雖然每種操作的執行時間皆有所不同，但對於估計程式的執行效率或時間，有很大的幫助。

### 以操作數切入複雜度

給定一個長度為 $N$，元素不重複的整數序列 $X$，現有 $Q$ 筆詢問，每次詢問給定一個元素，要求回答該元素在序列 $X$ 中的位置（索引值）。

#### 算法一：將 $X$ 以原形式儲存

對於每筆詢問，只需遍歷（traverse）$X$，並逐一比對元素，直至找到給定元素。

#### 算法二：建立一個元素位置表 $P$

首先，我們事前記錄每個元素在序列 $X$ 中的索引值，將其建立成一個位置表 $P$，即值為 $i$ 的元素在 $X$ 中的索引值為 $P_i$。

表 $P$ 建成後，對於每筆詢問，你只需將給定的數字放進表 $P$ 中對照，即可在一個操作內得知其在 $X$ 中的位置。

#### 算法比較

這兩種算法都是合理的解題邏輯，然而後者在處理大規模測資實則較有效率。為什麼呢？

1. 在算法一中，考慮每筆詢問都是最糟的情況，那麼我們就需要從頭到尾遍歷 $X$。操作數為 $N$。
2. 在算法二中，不論給定元素為何，都只需要一個索引操作，就可以得知該元素在 $X$ 中的索引值。操作數為 $1$。

因此，對於這個問題兩個算法的總操作數比較如下。

1. 算法一：輸入 $X$ 要 $N$ 次操作；每筆詢問都要 $N$ 次操作，共 $Q$ 筆詢問。總操作數 $N+QN$。
2. 算法二：輸入 $X$ 要 $N$ 次操作；建表需要 $N$ 次操作；每筆詢問都要 $1$ 次操作，共 $Q$ 筆詢問。總操作數 $2N+Q$。

哪個算法比較有效率？這會因 $N$ 和 $Q$ 的值而改變。
基本上，算法二在處理規模較大的測資會較有效率。

### 十的八次方法則

現代的線上評測系統（Online Judge）每秒約可執行 $10^8$ 筆操作。

因此，在解題時，與其想到算法後就馬上衝動地實作，你可以先利用十的八次方法則來進行簡單的評估。判斷對於此題給定的測資規模是否可以通過時間限制，以免白費時間實作一個根本就不可能通過時間限制的算法。

以此次作業「中國人排隊問題」為例：

- 測資規模
- 中國人數：$P=10^6$
- 詢問數：$M=2\times 10^5$

考慮兩個算法

1. 算法一：操作數為 $P+PM$
2. 算法二：操作數為 $2P+M$

誰較可能通過時間限制呢？把變數值帶入，就知道了！

1. 算法一：$P+PM=(10^6)+(10^6)(2\times 10^5)\approx 10^{11}$
2. 算法二：$2P+M=2(10^6)+2\times10^5\approx10^6$

由上方計算出的結果可以預估：

1. 算法一執行時間約為 ${10^{11}\over 10^8}=1000$（秒）
2. 算法二執行時間約為 ${10^6\over 10^8}=0.01$（秒）

## 回歸正題——作業提示

### 建議作法

- 維護「**組間排隊**」佇列
- `佇列<組別編號>`
- 用法：`Q.front()` 為隊伍最前端的組別
- 維護「**組內排隊**」佇列*們*
- `陣列<佇列<中國人編號>>`
- 用法：`Q[g]` 為第 $g$ 組的隊伍
- 維護「**沒有組的排隊**」佇列
- `佇列<中國人編號>`
- 用法：`Q.front()` 為隊伍中最前面沒有組別的中國人編號
- 建立「**中國人所屬組別**」表
- `陣列<組別編號>`
- 用法：`G[n]` 為 $n$ 號中國人所屬的組別編號
- 維護「**組別是否在排隊**」表
- `陣列<真假值>`
- 用法：`G[g]` 為第 $g$ 組是否至少有一人在排隊

### 常見問題

1. 把組別成員們整個用二維陣列存起來 `vector<vector<int>>`
- 問題：對於每筆詢問，找到一個中國人所屬的組別最糟需要 $10^6$ 次操作
2. 不維護「**組別是否在排隊**」的表
- 問題：對於每筆詢問，得知一個組別是否在排隊最糟需要 $N$ 次操作
3. 用陣列代替佇列
- 問題：陣列移除首端元素後，會需要將元素往前遞補，因此涉及共 $N$ 筆操作。

### 參考程式架構

#include "bits/stdc++.h"
using namespace std;
#define endl '\n'

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int T; cin >> T;
    for (int t = 0; t < T; ++t) {
        cout << "Line #" << t+1 << endl;
        
        宣告「人屬於哪個組別」的表
        宣告「組別是否在隊伍中」的表
        宣告「組別間排隊」的佇列
        宣告「組別內排隊」的佇列
        
        int N; cin >> N;
        for (int i = 0; i < N; ++i) {
            int K; cin >> K;
            for (int j = 0; j < K; ++j) {
                int Ki; cin >> Ki;
                建立「人屬於哪個組別」的表
            }
        }

        int M; cin >> M;
        for (int i = 0; i < M; ++i) {
            string op; cin >> op;
            if (op == "ENQUEUE") {
                int x; cin >> x;
                // 透過「人屬於哪個組別」的表，得知這個人是哪個組，或沒有組
                int group = 這個人所屬的組別編號;  
                if (這個人沒有組) {
                    在「組別間排隊」的佇列新增這個人（因為他自己一組）
                } else {
                    在「組別內排隊」的佇列新增這個人
                    if (這個人所屬的組別不在隊伍中) {  // 透過「組別是否在隊伍中」的表，得知這個組別是否在隊伍中
                        將這個組新增至「組別間排隊」的佇列
                        更新「組別是否在隊伍中」的表
                    }
                }
            } else {
                if (「組別間排隊」的佇列首端的組別一個人自己一組) {
                    將這個人所屬的組別從「組別間排隊」的佇列移除
                    輸出這個人的編號
                } else {
                    將這個人從「組別內排隊」的佇列移除
                    if (這個人所屬的組別沒有人在排隊了) {
                        更新「組別是否在隊伍中」的表
                        把這個組從「組別間排隊」的佇列移除
                    }
                    輸出這個人的編號
                }
            }
        }
    }

    return 0;
}