搜尋與排序

Wiwi Ho

tags: CRC

https://hackmd.io/@wiwiho/crc1082algo
https://tg.pe/xgaG


比大小


怎麼比大小


全序關係


記作 \(\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


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 版

struct Comp{ bool operator()(T a, T b){ return /*...*/; } }; //... vector<T> a; sort(a.begin(), a.end(), Comp()); set<T, Comp> s;

function 版

bool comp(T a, T b){ return /*...*/; } //... vector<T> a; sort(a.begin(), a.end(), comp);

lambda 版

vector<T> a;
sort(a.begin(), a.end(), [](T a, T b){return /*...*/;});

搜尋


二分搜尋法


猜數字?


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\)
保證有解


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

\(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 定義小於)的元素位置


三分搜尋法


二分搜:把範圍分兩段
三分搜:把範圍分三段


分隔點


範例


有一開口向上的二次函數 \(f(x)\)
求頂點


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 裡的排序

sort(l, r, comp)

氣泡排序


分成已排序部分和未排序部分


一開始整個序列都是未排序的


找到未排序部分裡最大的元素
移到未排序部分的尾端


實作方式

第一個元素和第二個元素比較
第一個元素比較大就交換
第二個元素和第三個比較
如果第二個比較大就交換…… 未排序部分的倒數第二個元素和倒數第一個元素比較
倒數第二個比較大就交換


然後最後一個元素會加入已排序部分
未排序部分的大小少 1
接著重複一樣的動作
直到排序完為止


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
然後重複一樣的動作


實作方式

暴力


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)\)
再把兩邊合併


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)\)



\(O(n \log n)\)


快速排序


和合併排序相似
把範圍分兩邊分別排序
但不是直接切中間


選一個元素當 pivot
比它小的元素都放到它左邊
比它大的元素都放到它右邊

兩側遞迴排序


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,讓每個元素長不一樣


基數排序


非比較排序


從數字最低位開始看
拿十個桶子
最低位是幾就放第幾個桶子


從編號小的桶子開始依序拿出
放回序列
序列會按最低位排序


看次低位
也拿十個桶子
這一位是幾就放第幾個桶子
序列會按次低位排序,相同的按最低位


一直往高位看


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

\(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)\) 排序


#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;
}
Select a repo