Time Complexity & STL - HackMD

<style> .reveal .slides { text-align: left; font-size:30px; } </style> ## Time Complexity & STL 9/22 preTrain ---- <div style="font-size:21px"> - Time Complexity - How to estimate? - Some Examples </div> ---- <div style="font-size:21px"> - Commonly Used Function - math related function - min / max / swap - fill - sort - compare function - reverse - next / prev_permutation - islower / isupper / isdigit / isalpha / tolower / toupper - nth_element - lower_bound / upper_bound - unique - STL - iterator - pair / tuple - vector - priority_queue - stack / queue - set / multiset - map / multimap - bitset - list </div> ---- ## 語法查詢網站 - [Cplusplus](https://cplusplus.com/) - [Cppreference](https://en.cppreference.com/w/) --- ## 時間複雜度 ### Time Complexity - 與**輸入大小**有關的函數 - 可以用來估計程式執行大約的時間 - 用程式執行次數來去估算執行時間 - 通常以大 $O$ 符號表式，ex: $O(N)$、$O(N\log M)、O(k^3)$ ---- ### 計算大概的執行次數執行次數無法完全精準的計算可能受到編譯器優化影響使得執行次數不是我們所計算的而只需要計算大概的次數就可以去估算時間 ---- ### 表達時間複雜度 - 以大$O$符號表示，其中大$O$符號代表 "上限" 的意思 ---- ### 計算時間複雜度 1. 估計程式的運算執行次數 $\to$ 可能是個多項式 : $p=an^2+bn+c$ 3. 將得到的函數最高階項以外的項全部刪掉 $\to an^2$ 4. 把係數拿掉 $\to n^2$ ---- ### 迴圈的時間複雜度迴圈的執行次數 $\times$ 每次迴圈的時間複雜度 ```cpp for(int i = 0; i < n; i++) { // n arr[i] = arr[i - 1] * a + b; // O(1) swap(a, b); // O(1) } ``` $n\times (O(1)+ O(1))=n\times O(1)=O(n)$ ---- ```cpp for(int i = 0; i < n; i++) { // n for(int j = i + 1; j < n; j++) { // n - i if(arr[i] > arr[j]) swap(arr[i], arr[j]); // O(1) } } ``` 執行次數大約是 : $$ \begin{split} &(n-1)+(n-2)+\cdots+1\\ &=\frac{1}{2}n(n-1)\\ &=\frac{1}{2}n^2+\frac{1}{2}n=O(n^2) \end{split} $$ ---- ```cpp for(int i = 1; i < n; i *= 2) s += i; ``` 設迴圈執行次數為 $k$ $$ \max i=2^k \lt n\quad \stackrel{取 \log_2}{\Longrightarrow}\quad k\lt \lg n $$ 因此是 $O(\log n)$ 在算複雜度時，通常 $\log$ 代表以 $2$ 為底，即 $\log_2$ (有時寫 $\lg$) ---- ### 遞迴函數的時間複雜度 - 簡單的你們應該會算(?) - 其他方法就留給演算法必修課去學 - 比較難的等教分治法(Divide&Conquer)時再說 - 很複雜的需要用到很難的函數設計技巧 ~~我也不會~~ ---- ### 內建函數的時間複雜度其實從函數的功能應該可以猜出其複雜度不然的話就把它記起來(至少常用的函數要知道) - memset : $O(N)$ - sort : $O(N\lg N)$ - \_\_gcd : $O(\log N)$ - lower_bound : $O(\log N)$ $\cdots$ 等一下會講這些函數怎麼使用 ---- ## 為什麼要學時間複雜度 - 對演算法的**執行時間**與**資料量**的關係有個概念 - 判斷一個程式 (做法) 會不會 **TLE** - 可以用測資的範圍去反推演算法 ---- 1. 把時間複雜度的大 $O$ 符號拿掉，並將題目給定的輸入範圍**上限**帶入函數，令得到的數值為 $T$ 2. 一般而言假設 c++ 每秒能跑 $10^8$ 的數量級 3. 假設題目的時限是 $\hat{T}$ 秒，那麼 - 若 $T\lt \hat{T}\times 10^8$則通常不會TLE - 若 $T\gt \hat{T}\times 5\times 10^8$ 則極有可能拿到TLE ---- ### 時間複雜度的好處 - 當你想到一個做法後，在開始寫之前就能先用時間複雜度來判斷是否會 TLE，以避免浪費時間在寫必然會 TLE 的程式 - 在比賽中更容易作時間分配、難度分析 --- ## 常用的函數 ---- ## math related function - abs(x) 回傳x的絕對值 - sqrt(x) 回傳x的平方根 (浮點數) - pow(a,x) 回傳a的x次方 (浮點數) - ceil(x)/floor(x)/round(x) 回傳 x 向上取整/向下取整/四捨五入 ---- ## 三角函數三角函數 $\cos(x)$, $\sin(x)$, $\tan(x)$ 反三角函數 $\text{acos}(x)$, $\text{asin}(x)$, $\text{atan}(x)$, $\text{atan}2(y, x)$ 數值單位全部都是弧度(radian) : $\text{角度}=\cfrac{弧度\times 180}{\pi}$ 常用 $\pi = \text{acos}(-1)$ ``` #define PI acos(-1) ``` ---- ## 指對數系列 - exp(x) 自然底數 e 的 x 次方 - log(x) 以 e 為底的對數 - log10(x) 以 10 為底的對數 - log2(x) 以 2 為底的對數要換底請用換底公式 ---- ## 比大小 ### min/max ```cpp= #include<algorithm>//min/max min(a, b) min({a, b, c}) max(a, b) max({a, b, c, d}); ``` ---- ## 交換值 ```cpp= #include<algorithm> swap(a, b) ``` ---- ## GCD 最大公因數 (需 c++14 後才能使用) ```cpp #includ<algorithm> //gcd #include<iostream> int main(){ int a, b; cin >> a >> b; cout << __gcd(a, b) << endl; } ``` $$ a \text{ 和 } b \text{ 的最小公倍數} = \cfrac{a \cdot b}{\gcd(a, b)} $$ ---- ## fill 把區間 [l, r) 的值都設成 x，l, r 為指標或者迭代器 ``` #include<iostream> #include<algorithm> int main(){ int n = 5; int arr[8]={0,1,2,3,4,5,6,7}; fill(arr+1, arr+5, 10); } ``` arr 的結果為 {0,10,10,10,10,5,6,7} ---- ## sort 用法排序區間 [l, r)，l, r 為指標或者迭代器，複雜度為 $O(n\log n)$ ``` sort(l, r); ``` ### 範例 ```cpp= #include<iostream> #include<algorithm> // sort int arr[48763]={4, 8, 7, 6, 3}; int main(){ sort(arr,arr+5); } ``` 結果為 3, 4, 6, 7, 8 ---- ## 自訂比較關係如果不想由小排到大，想由大排到小? ---- 寫一個函式，告訴編譯器你要怎麼排! ---- ## compare function 傳入兩個參數 lhs, rhs，作為比較對象 lhs(left hand side) : 代表較左邊的元素 rhs(right hand side) : 代表較右邊的元素可以想成希望在左邊的元素大於右邊的元素， ```cpp= #include<iostream> #include<algorithm> // sort bool cmp(int lhs, int rhs){ // compare function return lhs > rhs; } int arr[5] = {3, 2, 7}; int main(){ sort(arr, arr+3, cmp); } ``` ---- 想省行數的話也可以寫在一起 ```cpp sort(arr, arr+3, [](int lhs, int rhs){ return lhs > rhs; }); ``` ---- ## 例題 ### [UVA11321 — Sort! Sort!! and Sort!!!](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2296) 給你 $n$ 個整數與整數 $m$，排序順序如下 : 1. 按照$\mod m$ 由小到大 2. 餘數相等則奇數在偶數前面 3. 如果同為奇數則由大到小 4. 如果同為偶數則由小到大 ---- ## 比較函式 1. 按照$\mod m$ 由小到大 2. 餘數相等則奇數在偶數前面 3. 如果同為奇數則由大到小 4. 如果同為偶數則由小到大 ```cpp= bool cmp(int lhs, int rhs){ if((lhs % m) != (rhs % m)) return (lhs % m) < (rhs % m); if ((lhs%2) != (rhs%2)) return (lhs%2) > (rhs%2); if(lhs%2) return lhs > rhs; else return lhs < rhs; } ``` ---- ## reverse 把區間 [l, r) 翻轉，l, r 為指標或迭代器 ```cpp= #include<algorithm> //reverse int arr[5] = {1,2,3,4,5}; reverse(arr, arr+5); ``` arr 的結果為 \{5,4,3,2,1\} ---- ## next / prev_permutation - next_permutation 產出的下一個排列都會比原本的字典序還大，而 prev_permutation 則相反 - 如果一開始的排列是字典序最小的，就可以用 next_permutation 產生出全部的排列。 ---- ## 用法產生區間 [l, r) 的下一個排列，若不存在則回傳 false，反之回傳 true 均攤複雜度 $\Omega(1)$，最差 $O(n)$ input ``` 1 3 2 ``` result ``` 2 1 3 ``` ---- ```cpp= #include<algorithm> int arr[4] = {3,2,4,1}; next_permutation(arr, arr+4); ``` result ``` 3 4 1 2 ``` ---- ### 產生所有排列如果序列一開始為最小字典序，透過 next_permutation 不斷變成下一大的順序，可以產生所有排序 ```cpp= int n = 3; int arr[3] = {1, 2, 3}; do{ for(int i = 0; i < n; i++) cout << arr[i] << " \n"[i+1==n]; } while(next_permutation(arr, arr + n)); ``` #### 輸出： ``` 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 ``` ---- ## 判斷/轉換字元 ```cpp #include<cctype> ``` - islower\(c\) 判斷字元 c 是否為小寫字母 - isupper\(c\) 判斷字元 c 是否為大寫字母 - isalpha\(c\) 判斷字元 c 是否為字母 - isdigit\(c\) 判斷字元 c 是否為數字 - tolower\(c\) 回傳字元 c 的小寫字母 - toupper\(c\) 回傳字元 c 的大寫字母 ---- ## nth_element ```cpp nth_element(l, l+k, r) ``` 將此區間 [l, r) 第 k 小的數放在左邊數來第 k 個位置，且 [l , k) 皆比 k 小，(k , r) 皆比 k 大，但這兩個區間內是無序的 ---- ## 範例 ```cpp= int arr[1e5+5]={}; bool cmp(int x,int y){ return x>y; //更改為降序排列 } int main(){ for(int i=1;i<=100;i++) arr[i]=i; nth_element(arr+1,arr+50+1,arr+100+1); } ``` 結果 : 1~49 (無序排列) , 50 , 51~100 (無序排列) - 複雜度為平均 $O(n)$ - 可以加入第四個函數傳入自訂比較函數 ```cpp nth_element(l, l+k, r, cmp) ``` ---- ## 例題 --- [CF 412B](https://codeforces.com/problemset/problem/412/B) 題意: 給你 N 個數字，以及 K，求出第 K 大的數字是多少 ``` 6 4 100 20 40 20 50 50 ``` 答案為40 ---- ## 實作 ```cpp= #include <algorithm> #include <iostream> using namespace std; int n, k, a[100005]; int main() { cin >> n >> k; for (int i = 0; i < n; i++) cin >> a[i]; nth_element(a, a + (k - 1), a + n, greater<int>()); cout << a[k - 1] << '\n'; return 0; } ``` greater<> 為內建的大於比較函式 ---- ## lower_bound / upper_bound ### lower_bound(l, r, x) 找到區間 [l, r) 範圍內第一個**大於等於** x 的值的位置。 ### upper_bound(l, r, x) 找到區間 [l, r) 範圍內第一個**大於** x 的值的位置。 <br> 以上兩個函數裡面所尋找的區間必須為**已排序**的才可以正常使用如果沒找到則會回傳位置 r (最後一項的下一項) ---- ## 範例時間複雜度 $O(\log n)$ ```cpp= #include<iostream> #include<algorithm> using namespace std; int a[100005]; int main(){ int n,x; cin >> n; for(int i = 0; i < n; ++i) cin >> a[i]; sort(a, a + n); cin >> x; cout << lower_bound(a, a + n, x) - a << '\n'; cout << upper_bound(a, a + n, x) - a << '\n'; // 通過找到的位置減去起始位置 begin, 得到索引值 return 0; } ``` 一樣可以使用自訂比較函式 lower_bound ( first , last , value , cmp) upper_bound ( first , last , value , cmp) ---- ## unique 把區間內連續相同元素刪除到只留一個，回傳值為沒被刪除的元素的下一項指標/迭代器複雜度 $O(n)$ input ``` 4 2 1 1 1 5 2 2 4 4 ``` result ``` 4 2 1 5 2 4 x x x x ``` 注意原陣列大小不會改變，相異元素之後的值無法保證為何 ---- ## unique 用法 unique(l, r) : 將區間 [l, r) 內連續相同元素刪除到只留一個 ```cpp= #include<iostream> #include<algorithm> int n = 10, arr[10] = {4, 2, 1, 1, 1, 5, 2, 2, 4, 4}; int main(){ int k = unique(arr, arr + n) - arr; cout << k << endl; for(int i = 0; i < k; i++) cout << arr[i] << " \n"[i + 1 == k]; } ``` result ``` 6 4 2 1 5 2 4 ``` ---- 排序後再刪除，即可知曉整個陣列共出現幾種相異的數字作法 1. sort 區間 [l, r) 2. unique [l, r) 並記錄回傳的指標/迭代器 ---- ## 找相異數字結果為原始陣列**所有相異元素**並且**已排序** ```cpp= #include<iostream> #include<algorithm> int n = 10, arr[10] = {4, 2, 1, 1, 1, 5, 2, 2, 4, 4}; int main(){ sort(arr, arr + n); // 1. sort 區間 [l, r) int k = unique(arr, arr + n) - arr; // 2. unique [l, r) 並記錄回傳的指標/迭代器 cout << k << endl; for(int i = 0; i < k; i++) cout << arr[i] << " \n"[i + 1 == k]; } ``` result ``` 4 1 2 4 5 ``` ---- 此技巧常用於離散化 : - 一種把資料的數值變小 (重新編號) 的技巧 - 不影響到任兩資料的大小關係作法 : 1. 把一段的區間 [l, r) 的資料只留下相異的元素各一個 2. 再用原區間資料去做 lower_bound，並替換 ---- ## 陣列離散化 ```cpp= #include<iostream> #include<algorithm> int n = 10, arr[10] = {100, 5000, 100, 999999999, 42}; int tmp[10]; // 處理離散化的陣列 int main(){ for(int i = 0; i < n; i++) tmp[i] = arr[i]; // 把陣列站存在 tmp sort(tmp, tmp + n); int k = unique(tmp, tmp + n) - tmp; // 離散化後的長度 for(int i = 0; i < n; i++){ arr[i] = lower_bound(tmp, tmp + k, arr[i]) - tmp; } } ``` result ``` 4 1 2 1 3 0 ``` --- ## Iterator & STL container - pair / tuple - iterator - vector - stack / queue - set / multiset - map / multimap - priority_queue - bitset - list ---- ### pair / tuple 分別在 \<utility\> 和 \<tuple\> 中偷懶用資料結構，分別是可以用來宣告裝 2 個東西/多個東西的變數 ---- ### pair 常用來儲存二維平面上的點 (x, y) 之類 * 宣告 ```cpp pair<int,int> pair<double,int> ``` * 取值 ```cpp= pair<int,int> a a.first (可以取到第一個值) a.second (可以取到第二個值) ``` ---- 對 pair 的元素 sort，會先比較 first 大小，相同再比較 second 的大小 ```cpp= #include<iostream> #include<utility> using namespace std; pair<int, int> point[10]; int main(){ for(int i = 0; i < 5; i++) cin >> point[i].first >> point[i].second; sort(point, point+5); int a, b; point[0] = make_pair(a, b); } ``` ---- ### 使用範例：tuple * 宣告 ```cpp tuple<int, int, int> tuple<double, int, long double, ...(還可以塞很多東西)> ``` * 取值 ```cpp= tuple<int, int, int> a get<0>(a) (可以取到第一個值) get<2>(a) (可以取到第三個值) ``` ---- make_tuple 可以把元素合併成 tuple ```cpp #include<iostream> #include<tuple> using namespace std; tuple<string, int, int, double> item[10]; int main(){ string s; int a, b; double d; for(int i = 0; i < 5; i++){ cin >> s >> a >> b >> d; item[i] = make_tuple(s, a, b, d); } sort(item, item+5); tie(s, a, b, d) = item[0]; cout << s << " " << b << " " << d << " " << get<0>(item[1]) << endl; } ``` ---- ### Iterator 迭代器迭代器是用來遍歷容器的東西，由於有些容器不像陣列能用下標 (index) 遍歷，迭代器便能用來遍歷這類容器。 ---- c++ 的迭代器皆被實作的與指標相似，用遞增運算子 (\+\+it \/ it\+\+) 來移動到下一項，且用反指標運算子(*it)來取得當前項的值。多數還支援遞減運算子(\-\-it \/ it\-\-) 移動到前一項(稱作雙向迭代器) 有些支援隨機存取(random access)， +\/- 運算子(it+k \/ it-k) 一次能移動多項 ---- 對於一個容器，分別有代表頭尾的迭代器，其中頭代表首項，而尾代表最後一項的下一項，因此遍歷方式通常是for(it=begin;it!=end;it++) 對於陣列 (C-style array)，其迭代器就是指標，且頭尾分別是 arr/arr+n，對於 STL 內的容器，其迭代器是C::iterator，且頭尾分別是arr.begin() / arr.end() 此外STL內還有實作反向迭代器用來從最後一項開始往前遍歷，其形態是 C::reverse_iterator 頭尾分別是 arr.rbegin() / arr.rend() ---- ### vector ``` #include<vector> ``` 動態陣列。有時候我們無法預估陣列所需要宣告的長度，又必須宣告陣列，這時會選用 vector ---- - vector 的常用函式 : push_back , pop_back , size , empty , begin , end, clear, resize, assign - 須注意的是若等到 vector 空間不夠裝，vector 會自動安排記憶體，但這麼做常數比較大，所以通常在使用前會先預設一些記憶體位置給 vector * 我們會使用 reserve() 。e.g. `vector.reserve(100005)` * 或是直接在宣告時用建構元 (constructor) 指定大小。 e.g. `vector<int> vec(n)` - insert, erase 複雜度為 $O(n)$ ，請勿亂用 ---- 實際演練 : 常用函式 ```cpp= #include <iostream> #include <vector> // vector 的標題檔 using namespace std; int main() { vector<int> Mega; //宣告一個 vector 名稱叫 Mega 用來裝 int 元素 //裡面的容器是空的 for (int i=1; i<=5; i++) Mega.push_back(i); for (int i=5; i>=1; i--) Mega.push_back(i); cout << Mega.size() << "\n"; for (int i=1; i<=4; i++) Mega.pop_back();// 將 vector 尾端元素刪掉 cout << Mega.size() << "\n"; cout << Mega.empty() << "\n"; // empty() 函式為查詢 vector 裡面是否有元素 // 回傳值為 bool 1 裡面沒有元素 0 則是有 Mega.clear(); cout << Mega.empty() << "\n"; } ``` ---- 實際演練 : 使用 index 遍歷 ```cpp= #include <iostream> #include <vector> using namespace std; int main() { vector<char> roy; for (int i=0; i<26; i++) { char c = i + 'A'; roy.push_back(c); } for (int i=0; i<roy.size(); i++) { cout << roy[i] << " "; } cout << roy[5] << "\n"; cout << roy[0] << "\n"; // 查詢單一個元素可用陣列方式查詢 } ``` ---- 實際演練 : 遍歷 iterator 遍歷 ```cpp= #include <iostream> #include <vector> using namespace std; int main() { vector<int> vt; vector<int>::iterator iter; for (int i=95; i<=100; i++) { vt.push_back(i); } iter = vt.begin(); for(iter = vt.begin(); iter != vt.end(); iter++) { cout << *iter << "\n"; // 一定要「 * 」號 } } ``` ---- ### stack ``` #include<stack> ``` 堆疊是一種先進後出的結構，像是疊盤子一樣，先放下去的會最慢被拿出來。 ---- - stack的常用函式 : emplace(push) , size , empty , top , pop . - 不支援隨機存取：O(N) 查找速度慢：O(N) 在集合中增刪元素很快：O(1) ---- 實際演練: ```cpp= #include <iostream> #include <stack> // stack 的標題檔 using namespace std; int main() { stack<int> Stk; //宣告一個 stack 名稱叫 stk 用來裝int元素 //一開始裡面的容器是空的 for (int i=4; i<=10; i++) { Stk.push(i); } cout << Stk.top() << "\n"; // 輸出 stack 最上層的元素，所以會輸出 10 Stk.pop(); // 刪除 stack 最上層的元素 cout << Stk.top() << "\n"; // 輸出 stack 最上層的元素，所以會輸出 9 cout << "裡面有多少元素" <<Stk.size() << "\n"; // 查詢 stk 裡面有幾個元素，裡面元素有 4 5 6 7 8 9共六個，所以會輸出 6 cout << Stk.empty() << "\n"; // empty() 函式為查詢 stack 裡面是否有元素 // 回傳值為bool 1 裡面沒有元素 0 則是 //清除 stack的元素 while(Stk.size() != 0) { // 或是 while(Stk.empty == 0) Stk.pop(); } cout << "裡面有多少元素" << Stk.size() << "\n"; cout << Stk.empty() << "\n"; } ``` ---- ## 超經典例題 : 括弧匹配 **題目:** 給予一個字串並包含了括號 '[', ']', '(', ')' 和 '{', '}'，請驗證該字串中的括號是否合法配對。也就是 "([])", "{()}", "[]" 為合法配對，但是 "(]", 或 "([)]" 就是不合法配對。 **規律:** * 括號數量一定是偶數 * 有左邊系列括號，就一定有右邊系列括號 * 越慢出現的左邊括號，他的右邊括號就越早出現(順序相反)。 ---- ### queue ```cpp #include<queue> ``` 佇列是一種先進先出的結構，像是水管一樣的單向道，最早進去的會最先通出來。 ---- - queue 的常用函式 : push , size , empty , front , pop . - 不支援隨機存取：$O(N)$ 查找速度慢：$O(N)$ 在集合中增刪元素很快：$O(1)$ - 常用在 BFS ---- 實際演練: ```cpp= #include <iostream> #include <queue> // queue 的標題檔 using namespace std; int main() { queue<int> que; //宣告一個 queue 名稱叫 que 用來裝int元素 //一開始裡面的容器是空的 for (int i=4; i<=10; i++) { que.push(i); } cout << que.front() << "\n"; // 輸出 queue 最上層的元素，所以會輸出 4 que.pop(); // 刪除 queue 最上層的元素 cout << que.front() << "\n"; // 輸出 queue 最上層的元素，所以會輸出 5 cout << "裡面有多少元素" <<queue.size() << "\n"; // 查詢 queue 裡面有幾個元素，裡面元素有 5 6 7 8 9 10共六個，所以會輸出 6 cout << que.empty() << "\n"; // empty() 函式為查詢 queue 裡面是否有元素 // 回傳值為bool 1 裡面沒有元素 0 則是 //清除 queue的元素 while(que.size() != 0) { // 或是 while(que.empty == 0) que.pop(); } cout << "裡面有多少元素" << que.size() << "\n"; cout << que.empty() << "\n"; } ``` ---- ### 經典例題環節: 用兩個 stack 去實作出 queue 的功能 **作法:** - 始終維護 s1 作爲存儲空間，以 s2 作爲臨時緩衝區 - 入隊時，將元素壓入 s1 - 出隊時，將 s1 的元素逐個“倒入”（彈出並壓入）s2，將 s2 的頂元素彈出作爲出隊元素，之後再將 s2 剩下的元素逐個“倒回” s1 ![](https://i.imgur.com/Tu7RPsb.png) ---- ### priority_queue 可以很快很方便的加入元素或取出當前最優先的元素常用於優化複雜度 ---- * 在標頭檔 queue 裡面 * priority_queue 裡面可以塞 int , string , long long , 實作原理是 max_heap 在運作 * 為一序列容器是一個帶優先級的 queue * priority_queue 的常用函式 : push , size , empty , top , pop . ---- ### priority_queue 複雜度分析 * push() 新增元素，複雜度 $O(\log n)$ * size() 取得目前元素數量，複雜度 $O(1)$ * top() 取得目前最高優先（數值最大）的元素（不會刪掉），複雜度 $O(1)$ * pop() 刪掉目前最高優先（數值最大）的元素，複雜度 $O(\log n)$ ---- 實際演練: ```cpp= #include <queue> priority_queue<int> pq; priority_queue<int, vector<int>, greater<int> > pq1; //從小到大變成min_heap pq.push(5); pq.push(8); pq.push(4); // 元素可重複，會個別保留 pq.push(5); cout << pq.size() << "\n"; cout << pq.top() << "\n"; pq.pop(); cout << pq.size() << "\n"; cout << pq.top() << "\n"; cout << pq.empty() << "\n"; ``` ---- ### 題目演練: 動態中位數對每一個輸入，請輸出到現在為止已輸入的數的中位數。 ``` 輸入: 輸出: 1 1 3 2 4 3 60 3 70 4 50 27 2 4 ``` ---- ## 中位數維護兩個 pq(priority_queue)，其中一個 pq 維護大於等於中位數的數值另一個 pq 維護小於中位數的數值如此一來，中位數必定為大於等中位數那堆的最小值 ---- ## 取中位數大於等中位數的 pq 每次取最小值即為中位數 ```cpp priority_queue<int, vector<int>, greater<int>> big; cout << big.top() << endl; ``` ---- ## 加入一個新元素判斷當前加入的新元素 x 如果小於中位數，則加入維護小的 pq 否則加入維護大的 pq ```cpp if(x < big.top()) small.push(x); else big.push(x); ``` ---- ## 維護兩個 pq 的大小為了讓中位數固定在比較大的那堆的最小值，兩堆 pq 的大小至多只能差一因此每次新增完元素，如果小的那堆太多要把最大的元素丟過去大的那堆反過來則大的最小丟去小的那堆 ```cpp priority_queue<int> small; priority_queue<int, vector<int>, greater<int>> big; while(small.size() >= big.size()) big.push(small.top()), small.pop(); while(small.size()+1 < big.size()) small.push(big.top()), big.pop(); ``` ---- ### set (集合) ``` #include<set> ``` - 插入一個元素 - 從集合中刪除一個元素 - 查詢元素有沒有在集合裡面 - 查詢集合內最小/大值 - 查詢集合內 $> x$ 或 $\ge x$ 中的最小元素 ---- - set 是有序的，對 set 遍歷時，會以定義的大小順序遍歷，預設是由小到大 - 大多數操作皆為 $O(\log N)$ - set 的常用函式：insert, erase, count, size, empty, begin, end, lower_bound, upper_bound ---- ### 使用範例: 插入、刪除元素 ```cpp set<int> s; // [] s.insert(1); // s = [1] s.insert(5); // s = [1, 5] s.insert(3); // s = [1, 3, 5] s.insert(2); // s = [1, 2, 3, 5] s.insert(1); // s = [1, 2, 3, 5] s.erase(3); // s = [1,2,5] ``` ---- ### 使用範例: 插入、查詢元素 ```cpp set<pair<int,int> > s; //[] s.insert({1, 2}); // [{1, 2}] s.insert({2, 1}); // [{1, 2}, {2, 1}] s.insert({2, 1}); // [{1, 2}, {2, 1}] s.insert({3, 5}); // [{1, 2}, {2, 1}, {3, 5}] s.count({2, 1}); // return 1，代表 {2, 1} 有在集合內; s.count({5, 3}); // return 0 ``` ---- ### 使用範例: 插入元素、找最小/大值 ```cpp set<int> s; // [] s.insert(1); // s = [1] s.insert(5); // s = [1, 5] s.insert(3); // s = [1, 3, 5] s.insert(2); // s = [1, 2, 3, 5] cout << *s.begin() << endl; // 1 cout << *s.rbegin() << endl; // 5 ``` ---- ### 使用範例: 插入元素、找第一個大於等於 x 的元素如果沒找到則回傳 end() ```cpp set<int> s; // [] s.insert(1); // s = [1] s.insert(5); // s = [1, 5] s.insert(3); // s = [1, 3, 5] s.insert(2); // s = [1, 2, 3, 5] if(s.lower_bound(3) != s.end()) cout << s.lower_bound(3) << endl; else cout << "NOT FOUND" << endl; ``` ---- ### 使用範例: 插入元素、找第一個大於 x 的元素如果沒找到則回傳 end() ```cpp set<int> s; // [] s.insert(1); // s = [1] s.insert(5); // s = [1, 5] s.insert(3); // s = [1, 3, 5] s.insert(2); // s = [1, 2, 3, 5] if(s.lower_bound(3) != s.end()) cout << s.upper_bound(3) << endl; else cout << "NOT FOUND" << endl; ``` * lower_bound(s.begin(), s.end(), x) **複雜度為 $O(n)$** * s.lower_bound(x) 複雜度才是 $O(\log n)$ ---- ### map ``` #include<map> ``` 映射，基本上就是多了個對應值的set，單位型態為 pair<key,value> 用法跟 set 很像，但多了 operator[] 可以取值或存值。 ---- * 大多操作皆為 $O(\log n)$ * map 的常用函式：insert, erase, count, size, empty, begin, end, lower_bound, upper_bound. ---- ### 使用範例： ```cpp map<int, int> mp; mp[3] = 1; // [3] = 1, mp[2] = 2; // [2] = 2, [3] = 1; mp[3] = 5; // [2] = 2, [3] = 5; ``` ---- ### 使用範例： ```cpp map<string,int> mp; // map 還可以用 string 當 key mp["qwer"] = 1; mp["abc"] = 2; ``` ---- ### multiset / multimap * key 可以重複的 set / map * 由於 key 會重複，因此少了 [ ]operator * 大多操作皆為 $O(\log n)$ * 函式與 set / map 類似 ---- ### 使用範例： ```cpp multiset<int> s; // [] s.insert(1); // [1] s.insert(2); // [1, 2] s.insert(3); // [1, 2, 3] s.insert(1); // [1, 1, 2, 3] s.count(1); // return 2; s.erase(1); // [2, 3] ``` 使用 erase(x) 會把全部值為 x 的元素刪除如果只要刪除一個可以使用 s.erase(s.find(x)) 刪除 ---- ### 使用範例： ```cpp multimap<int, string> mp; // [] mp.insert({1, "c8763"}); mp.insert({1, "38763"}); mp.insert({2, "1919"}); mp.insert({4, "8100"}); mp.count(1); // return 2 ``` ---- ### bitset ```cpp #include<bitset> ``` 可看作是 bool 陣列，支援位元運算，且成員函數多為位元相關函數，用在位元運算常數非常小，沒有要做位元運算別亂用(用 vector\<bool\> 就好) ---- - 但長度必須是**常數** - 常用函式：count、size、test、any、none、all、set、reset、flip。 ---- ### 使用範例： ```cpp #include<bitset> //bitset #include<iostream> bitset<10> a = 7; bitset<10> b(10); bitset<10> c("10010"); int main(){ b = 5; //101 b >>= 1; //10 cout << b << endl; cout << (a|c) << " " << (a&c) << " " << (a^c) << endl; } ``` ---- ## list ```cpp #include<list> ``` C++ 內建的 linked-list，可以在 O(1) erase, insert 但沒有支援隨機存取(random access)，無法使用 index 查詢常用函數: push_back, push_front, pop_back, pop_front, insert, erase, size ---- ## 範例 ```cpp #include<list> #include<iostream> using namespace std; int main(){ list<int> arr; arr.push_back(3); // [3] arr.push_back(4); // [3, 4] list<int>::iterator iter = prev(arr.end()); // 儲存 arr 最後一個元素的iterator arr.push_back(1); // [3, 4, 1] arr.push_front(10); // [10, 3, 4, 1] arr.erase(iter); //[10, 3, 1] } ``` ---- ## 例題: 刪除元素 - 給一個長度為 $n$ 的排列，有 $q$ 筆操作，操作為每次把數字 x 以及左右相鄰的元素刪除，求最後序列的樣子 input ``` 8 2 1 5 8 3 6 4 7 2 3 4 ```` output ``` 1 2 ``` [1 5 8 3 6 4 7 2] $\to$ [1 5 4 7 2] $\to$ [1 2] ---- 暴力找某個元素的位置最差情況需要遍歷整個序列 $O(n)$ 但太慢了因此通常會搭配 map，把每個元素儲存在 list 中的位置儲存在 map 中 ```cpp #include<list> #include<iostream> using namespace std; int main(){ list<int> arr; map<int, list<int>::iterator> mp; int n; cin >> n; for(int i = 0, x; i < n; i++){ cin >> x; arr.push_back(x); mp[x] = prev(arr.end()); } } ``` ---- ### 移除操作: 把數字 x 以及左右相鄰的元素刪除 ```cpp= void remove(int x){ list<int>::iterator it = mp[x]; if(it != arr.begin()) arr.erase(prev(it)); if(next(it) != arr.end()) arr.erase(next(it)); arr.erase(it); } ``` ---- map 維護儲存、查詢為 $O(\log n)$， $q$ 筆操作總複雜度為 $O(q\log n)$ --- ## 時間複雜度範例分析 ---- ```cpp for(int i = 10; i < n; i++){ for(int j = i - 100; j >= 1000; j--) cout << i << " " << j << '\n'; } ``` $$ O(n^2) $$  ---- ```cpp for(int i = 0; i < 100000000; i++) cin >> n, cout<< n * n << '\n'; ``` $$ O(1) $$  ---- ```cpp for(int i = 1; i <= n; i++){ sort(arr, arr + i); // <algorithm> library 的通用排序 } ``` $$ \sum\limits_{k=1}^{n}k\lg k\approx n^2\lg n=O(n^2\lg n) $$  這要視排序法而定，但是原函式還是 $O(n^2\lg n)$  ---- ```cpp for(int i = 1; i < n; i = i * 2){ for(int j = i; j < n; j += i) arr[j] += arr[j - i]; } ``` $$ n+\frac{n}{2}+\frac{n}{4}+...\approx 2n=O(n) $$  ---- ```cpp void f(int n){ if(n == 0) return 1; return f(n - 1) * n; } ``` $$ O(n) $$  ---- ```cpp void f(int i){ if(i==n) return; v[i] = 0, f(i+1); v[i] = 1, f(i+1); v[i] = 2, f(i+1); } ``` $$ O(3^n) $$  ---- ```cpp set<int> s; for(int i = 0, tmp; i < n; i++){ cin >> tmp; s.insert(tmp); } ``` $$ \begin{split} \sum_{k=1}^{n}\log k &=\log 1+\cdots+\log n=\log (1\times\cdots\times n)\\ &\leq \log n^n=n\log n=O(n\log n) \end{split} $$  --- 建議每種 STL 語法都套過題目一遍試試看，以免比賽中要用到不會用不用硬背起來，要用到再查語法，多寫幾次自然後就記得了。 [Problem List](https://vjudge.net/contest/749722#overview)