搜尋與排序 - HackMD

# 搜尋與排序 Wiwi Ho ###### tags: `CRC` --- https://hackmd.io/@wiwiho/crc1082algo https://tg.pe/xgaG ![](https://i.imgur.com/KqGWkCw.png) --- # 比大小 --- ## 怎麼比大小 ---- ## 全序關係 ---- 記作 $\leq$ 就是常見的比較符號 ---- 但意義不一定是平常說的小於等於這裡的 $\leq$ 就純粹是一種符號沒有固定的意義 ---- 某集合 $X$ 滿足全序關係的條件： - $\forall a,b \in X, a \leq b \land b \leq a \Rightarrow a = b$ - $\forall a,b,c \in X, a \leq b \land b \leq c \Rightarrow a \leq c$ - $\forall a,b \in X, a \leq b \lor b \leq a$ ---- 也就是說，$X$ 內的每一對元素要可以互相比較 ---- ## 非嚴格全序 ---- 記作 $<$ 就是 $\leq$ 少 $=$ ---- 性質： - $\forall a,b,c \in X, a < b \land b < c \Rightarrow a < c$ - $\forall a,b \in X, a < b \lor b < a \lor a = b$ ---- ## 偏序關係 ---- 也記為 $\leq$ ---- 性質： - $\forall x \in X, x \leq x$ - $\forall a,b \in X, a \leq b \land b \leq a \Rightarrow a = b$ - $\forall a,b,c \in X, a\leq b \land b \leq c \Rightarrow a \leq c$ ---- 和全序的差別是偏序關係不需要每一對元素都能互相比較 ---- ## 單調性 ---- 函數 $f: X \to Y$ ---- 非嚴格遞增 $\forall x_1,x_2 \in X \land x_1 \leq x_2, f(x_1) \leq f(x_2)$ ---- 嚴格遞增 $\forall x_1,x_2 \in X \land x_1 \leq x_2, f(x_1) < f(x_2)$ ---- 非嚴格遞減 $\forall x_1,x_2 \in X \land x_1 \leq x_2, f(x_1) \geq f(x_2)$ ---- 嚴格遞減 $\forall x_1,x_2 \in X \land x_1 \leq x_2, f(x_1) > f(x_2)$ --- ## Comparator ---- 用來定義比較方式的 function 放在跟比較有關的 function 的參數和 container 的 template ---- ```cpp= vector<int> a; sort(a.begin(), a.end()); //把 a 裡的東西由小到大排序 sort(a.begin(), a.end(), less<>()); //把 a 裡的東西由小到大排序 sort(a.begin(), a.end(), greater<>()); //把 a 裡的東西由大到小排序 set<int> s1; //s1 裡的東西會由小到大排序 set<int, less<>> s2; //s2 裡的東西會由小到大排序 set<int, greater<>> s3; //s3 裡的東西會由大到小排序 ``` ---- ## less<>、greater<> STL 提供的 comparator 表示使用 $<$ 和 $>$ 運算子 ---- ## 自己實作 ---- struct 版 ```cpp= struct Comp{ bool operator()(T a, T b){ return /*...*/; } }; //... vector<T> a; sort(a.begin(), a.end(), Comp()); set<T, Comp> s; ``` ---- function 版 ```cpp= bool comp(T a, T b){ return /*...*/; } //... vector<T> a; sort(a.begin(), a.end(), comp); ``` ---- lambda 版 ```cpp vector<T> a; sort(a.begin(), a.end(), [](T a, T b){return /*...*/;}); ``` --- # 搜尋 --- ## 二分搜尋法 ---- 猜數字？ ---- ```cpp int l = /*初始下界*/, r = /*初始上界*/; while(l < r){ int m = (l + r) / 2; if(check(m)) //變更邊界 else //變更邊界 } ``` ---- 變更邊界 - $l=m$ - $r=m$ - $l=m+1$ - $r=m-1$ ---- 怎麼選 $m$ 如果有狀況會把 $l$ 變更成 $m$ 當 $l+1=r$ 時，$m=\lfloor\frac{2l+1}{2}\rfloor=l$ 範圍會卡住改成 $m=\lfloor\frac{l+r+1}{2}\rfloor$ ---- ## 範例 ---- 給遞增數列 $a_1 \leq a_2 \leq a_3 \leq ... \leq a_n$ 和數字 $x$ 求最小的 $i$ 滿足 $a_i \geq x$ 保證有解 ---- ```cpp vector<int> a(n); int x; //... int l = 0, r = n - 1; while(l < r){ int m = (l + r) / 2; if(a[m] >= x) r = m; else l = m + 1; } ``` ---- ## 時間複雜度 ---- 每次範圍大小變為本來的約一半 $\Rightarrow$ 時間複雜度 $O(\log_2 n)=O(\log n)$ ---- ## 對答案二分搜 ---- [ZeroJudge c575](https://zerojudge.tw/ShowProblem?problemid=c575) 有 $N$ 個服務點你最多可以放 $K$ 個基地台並決定一個盡量小的半徑 $R$ 使每一個服務點都有一個距離它至多 $R$ 的基地台求最小的 $2R$ ---- 如果 $R=x$ 時可以找到放基地台的方法那 $R>x$ 時也可以 $\Rightarrow$ 二分搜最小的可以找到怎麼放基地台的 $R$ ---- 怎麼找？盡量把基地台往後放 ---- ## STL 裡的二分搜 ---- lower_bound(l, r, n, comp) 回傳 $[l,r)$ 中第一個不小於 $n$（由 comp 定義）的元素位置 ---- upper_bound(l, r, n, comp) 回傳 $[l,r)$ 中第一個大於 $n$（由 comp 定義小於）的元素位置 --- ## 三分搜尋法 ---- 二分搜：把範圍分兩段三分搜：把範圍分三段 ---- 分隔點 ![](https://i.imgur.com/f3a8MGk.png) ---- ## 範例 ---- 有一開口向上的二次函數 $f(x)$ 求頂點 ---- ```cpp= double l = -1e9, r = 1e9; while(r - l > 1e-4){ double m1 = (2 * l + r) / 3; double m2 = (l + 2 * r) / 3; if(f(m1) < f(m2)) r = m2; else l = m1; } cout << l << " " << r << "\n"; ``` --- # 排序 --- ## STL 裡的排序 ```cpp sort(l, r, comp) ``` --- ## 氣泡排序 ---- 分成已排序部分和未排序部分 ---- 一開始整個序列都是未排序的 ---- 找到未排序部分裡最大的元素移到未排序部分的尾端 ---- 實作方式第一個元素和第二個元素比較第一個元素比較大就交換第二個元素和第三個比較如果第二個比較大就交換…… 未排序部分的倒數第二個元素和倒數第一個元素比較倒數第二個比較大就交換 ---- 然後最後一個元素會加入已排序部分未排序部分的大小少 1 接著重複一樣的動作直到排序完為止 ---- ```cpp= vector<int> a(n); //... for(int i = 0; i < n - 1; i++){ for(int j = 0; j < n - i - 1; j++){ if(a[j] > a[j + 1]) swap(a[j], a[j + 1]); } } ``` ---- 複雜度 $O(n^2)$ --- ## 插入排序 ---- 同樣分成已排序部分和未排序部分但通常未排序部分會放前面 ---- 在未排序部分裡找隨便一個數字再找到它應該放在已排序部分的哪裡然後塞進去未排序部分大小會少 1 然後重複一樣的動作 ---- 實作方式暴力 ---- ```cpp= vector<int> a(n); //... for(int i = 1; i < n; i++){ int pos = i; for(int j = i + 1; j < n; j++){ if(a[j] < a[pos]) pos = j; } int p; for(p = 0; p < i; p++){ if(a[p] > a[pos]) break; } int t = a[pos]; for(int j = pos; j > p; j--) a[j] = a[j - 1]; a[p] = t; } ``` ---- 時間複雜度 $O(n^2)$ --- ## 合併排序 ---- 把序列切兩半分別排序過後再合併 =某種遞迴 ---- $\text{mergesort}(l,r)$：將 $[l,r]$ 範圍排序 $m=\frac{l+r}{2}$ 呼叫 $\text{mergesort}(l,m)$ 和 $\text{mergesort}(m + 1, r)$ 再把兩邊合併 ---- ```cpp= void mergesort(vector<int>& a, int l, int r){ if(l == r) return; int m = (l + r) / 2; mergesort(a, l, m); mergesort(a, m + 1, r); vector<int> b; int lp = l, rp = m + 1; while(lp <= m && rp <= r){ if(a[lp] <= a[rp]) b.eb(a[lp]), lp++; else b.eb(a[rp]), rp++; } while(lp <= m) b.eb(a[lp]), lp++; while(rp <= r) b.eb(a[rp]), rp++; for(int i = 0; i < r - l + 1; i++) a[l + i] = b[i]; } //... vector<int> a(n); //... mergesort(a, 0, n - 1); ``` ---- 時間複雜度 ---- 遞迴到相同深度的範圍不會重疊且聯集是整個序列 ---- 遞迴深度每遞迴一層範圍大小會少約一半 $O(\log n)$ ---- ![](https://i.imgur.com/8io8MHr.png) ---- $O(n \log n)$ --- ## 快速排序 ---- 和合併排序相似把範圍分兩邊分別排序但不是直接切中間 ---- 選一個元素當 pivot 比它小的元素都放到它左邊比它大的元素都放到它右邊兩側遞迴排序 ---- ```cpp= void quicksort(vector<int>& a, int l, int r){ if(l >= r) return; int pv = /*...*/; swap(a[pv], a[r]); int lp = l, rp = r - 1; while(lp < rp){ while(lp < rp && a[lp] <= a[r]) lp++; while(lp < rp && a[rp] > a[r]) rp--; swap(a[lp], a[rp]); } if(a[rp] <= a[r]) rp = r; swap(a[rp], a[r]); quicksort(a, l, rp - 1); quicksort(a, rp + 1, r); } //... vector<int> a(n); //... quicksort(a, 0, n - 1); ``` ---- 複雜度 ---- 遞迴到一樣深度的範圍不重疊聯集也是整個序列 $\Rightarrow$ 複雜度是遞迴深度 $\times O(n)$ ---- 遞迴深度？和遞迴一層，範圍如何改變有關 ---- 如果每次範圍少 1 深度就是 $O(n)$ ---- 如何選 pivot？選定點：很好構出每次範圍少 1 的 case Random! ---- 有 $\frac{1}{2}$ 機率選到中間 50% 的元素 i.e. 比它小至少 25%、比它大至少 25% 範圍最多變 $\frac{3}{4}$ ---- 要選到最多 $\log_{\frac{4}{3}} n=\frac{log_2 n}{log_2 \frac{4}{3}} \approx 2.409 \log_2 n$ 次滿足條件的 pivot ---- 選到的機率是 $\frac{1}{2}$ $\Rightarrow$ 約 $2 \times 2.409 \log_2 n$ 次就可選到 $2.409 \log_2 n$ 次遞迴深度 $=O(2 \times 2.409 \log_2 n)=O(\log n)$ 複雜度 $O(n \log n)$ ---- 如果沒有這樣的元素能當 pivot？ ---- 如果幾乎所有元素都一樣那和 pivot 一樣的元素一定會被丟到同一邊 $\Rightarrow$ 變 $O(n^2)$ ---- 解決方法換成 pair，讓每個元素長不一樣 --- ## 基數排序 ---- 非比較排序 ---- 從數字最低位開始看拿十個桶子最低位是幾就放第幾個桶子 ---- 從編號小的桶子開始依序拿出放回序列序列會按最低位排序 ---- 看次低位也拿十個桶子這一位是幾就放第幾個桶子序列會按次低位排序，相同的按最低位 ---- 一直往高位看 ---- ```cpp= vector<int> a; //... vector<pair<int, int>> t(a.size()); for(int i = 0; i < a.size(); i++) t[i] = make_pair(a[i], a[i]); while(max_element(t.begin(), t.end())->F > 0){ vector<vector<pair<int, int>>> b(10); for(auto i : t) b[i.F % 10].emplace_back(i); t.clear(); for(int i = 0; i < 10; i++){ for(auto j : b[i]){ t.emplace_back(make_pair(j.first / 10, j.second)); } } } for(int i = 0; i < a.size(); i++) a[i] = t[i].S; ``` ---- 複雜度 ---- 令 $x=2^{63}-1=$ long long 最大值會看 $log_{10} x$ 位，$O(\log_{10} x)$ 看每一位時掃 $10+1$ 次數列，算作 $O(10n)$ 總複雜度 $O(10n \log_{10} x)=O(n)$？ ---- 常數 $10 \log_{10} x \approx 190$ ---- 用別的底？ $O(bn \log_b x)$ 常數：$b \log_b x$ ---- 不管怎樣都很大 --- ## 例題 ---- [ZeroJudge c471](https://zerojudge.tw/ShowProblem?problemid=c471) 有 $N$ 個物品你必須把它們疊起來成本是 $\sum_{i=1}^N f(i) \times \sum_{j=\text{所有在它上面的東西} w(j)}$ 最小化成本 ---- 只有兩個物品時如果 1 在 2 上方成本：$w(1) \times f(2)$ 如果 2 在 1 上方成本：$w(2) \times f(1)$ ---- 如果 $w(1) \times f(2) < w(2) \times f(1)$ 1 就要在 2 上面移項 $\frac{w(1)}{f(1)} < \frac{w(2)}{f(2)}$ 某種全序關係？ ---- 在一種堆疊順序中相鄰的兩個物品交換和其他物品相對位置不變所以對成本的改變只和它們有關 ---- 如果 $i$ 在上 $j$ 在下若 $\frac{w(i)}{f(i)} > \frac{w(j)}{f(j)}$ 把它們交換後成本會變小 ---- 按 $w(i) \times f(j) < w(j) \times f(i)$ 排序 ---- ```cpp #include <bits/stdc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); typedef long long ll; using namespace std; vector<ll> f, w; bool comp(int i, int j){ return w[i] * f[j] < w[j] * f[i]; } int main(){ StarBurstStream int n; cin >> n; f.resize(n); w.resize(n); for(int i = 0; i < n; i++) cin >> w[i]; for(int i = 0; i < n; i++) cin >> f[i]; vector<int> a(n); for(int i = 0; i < n; i++) a[i] = i; sort(a.begin(), a.end(), comp); ll ans = 0; ll sum = 0; for(int i = 0; i < n; i++){ ans += sum * f[a[i]]; sum += w[a[i]]; } cout << ans << "\n"; return 0; } ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.