並查集複雜度
本部分內容轉載並修改自 時間複雜度 - 勢能分析淺談，已取得原作者授權同意。
定義
阿克曼函數
這裏，先給出 \(\alpha(n)\) 的定義。為了給出這個定義，先給出 \(A_k(j)\) 的定義。
定義 \(A_k(j)\) 為：
即阿克曼函數。
這裏，\(f^i(x)\) 表示將 \(f\) 連續應用在 \(x\) 上 \(i\) 次，即 \(f^0(x)=x\)，\(f^i(x)=f(f^{i-1}(x))\)。
再定義 \(\alpha(n)\) 為使得 \(A_{\alpha(n)}(1)\geq n\) 的最小整數值。注意，我們之前將它描述為 \(A_{\alpha(n)}(\alpha(n))\geq n\)，反正他們的增長速度都很慢，值都不超過 4。
基礎定義
每個節點都有一個 rank。這裏的 rank 不是節點個數，而是深度。節點的初始 rank 為 0，在合併的時候，如果兩個節點的 rank 不同，則將 rank 小的節點合併到 rank 大的節點上，並且不更新大節點的 rank 值。否則，隨機將某個節點合併到另外一個節點上，將根節點的 rank 值 +1。這裏根節點的 rank 給出了該樹的高度。記 x 的 rank 為 \(rnk(x)\)，類似的，記 x 的父節點為 \(fa(x)\)。我們總有 \(rnk(x)+1\leq rnk(fa(x))\)。
為了定義勢函數，需要預先定義一個輔助函數 \(level(x)\)。其中，\(level(x)=\max(k:rnk(fa(x))\geq A_k(rnk(x)))\)。當 \(rnk(x)\geq1\) 的時候，再定義一個輔助函數 \(iter(x)=\max(i:rnk(fa(x))\geq A_{level(x)}^i(rnk(x))\)。這些函數定義的 \(x\) 都滿足 \(rnk(x)>0\) 且 \(x\) 不是某個樹的根。
上面那些定義可能讓你有點頭暈。再理一下，對於一個 \(x\) 和 \(fa(x)\)，如果 \(rnk(x)>0\)，總是可以找到一對 \(i,k\) 令 \(rnk(fa(x))\geq A_k^i(rnk(x))\)，而 \(level(x)=\max(k)\)，在這個前提下，\(iter(x)=\max(i)\)。\(level\) 描述了 \(A\) 的最大迭代級數，而 \(iter\) 描述了在最大迭代級數時的最大迭代次數。
對於這兩個函數，\(level(x)\) 總是隨着操作的進行而增加或不變，如果 \(level(x)\) 不增加，\(iter(x)\) 也只會增加或不變。並且，它們總是滿足以下兩個不等式：
考慮 \(level(x)\)、\(iter(x)\) 和 \(A_k^j\) 的定義，這些很容易被證明出來，就留給讀者用於熟悉定義了。
定義勢能函數 \(\Phi(S)=\sum\limits_{x\in S}\Phi(x)\)，其中 \(S\) 表示一整個並查集，而 \(x\) 為並查集中的一個節點。定義 \(\Phi(x)\) 為：
然後就是通過操作引起的勢能變化來證明攤還時間複雜度為 \(\Theta(\alpha(n))\) 啦。注意，這裏我們討論的 \(union(x,y)\) 操作保證了 \(x\) 和 \(y\) 都是某個樹的根，因此不需要額外執行 \(find(x)\) 和 \(find(y)\)。
可以發現，勢能總是個非負數。另，在開始的時候，並查集的勢能為 \(0\)。
證明
union(x,y) 操作
其花費的時間為 \(\Theta(1)\)，因此我們考慮其引起的勢能的變化。
這裏，我們假設 \(rnk(x)\leq rnk(y)\)，即 \(x\) 被接到 \(y\) 上。這樣，勢能增加的節點僅有 \(x\)（從樹根變成非樹根），\(y\)（秩可能增加）和操作前 \(y\) 的子節點（父節點的秩可能增加）。我們先證明操作前 \(y\) 的子節點 \(c\) 的勢能不可能增加，並且如果減少了，至少減少 \(1\)。
設操作前 \(c\) 的勢能為 \(\Phi(c)\)，操作後為 \(\Phi(c')\)，這裏 \(c\) 可以是任意一個 \(rnk(c)>0\) 的非根節點，操作可以是任意操作，包括下面的 find 操作。我們分三種情況討論。
- \(iter(c)\) 和 \(level(c)\) 並未增加。顯然有 \(\Phi(c)=\Phi(c')\)。
- \(iter(c)\) 增加了，\(level(c)\) 並未增加。這裏 \(iter(c)\) 至少增加一，即 \(\Phi(c')\leq \Phi(c)-1\)，勢能函數減少了，並且至少減少 1。
- \(level(c)\) 增加了，\(iter(c)\) 可能減少。但是由於 \(0<iter(c)\leq rnk(c)\)，\(iter(c)\) 最多減少 \(rnk(c)-1\)，而 \(level(c)\) 至少增加 \(1\)。由定義 \(\Phi(c)=(\alpha(n)-level(c))\times rnk(c)-iter(c)\)，可得 \(\Phi(c')\leq\Phi(c)-1\)。
- 其他情況。由於 \(rnk(c)\) 不變，\(rnk(fa(c))\) 不減，所以不存在。
所以，勢能增加的節點僅可能是 \(x\) 或 \(y\)。而 \(x\) 從樹根變成了非樹根，如果 \(rnk(x)=0\)，則一直有 \(\Phi(x)=\Phi(x')=0\)。否則，一定有 \(\alpha(x)\times rnk(x)\geq(\alpha(n)-level(x))\times rnk(x)-iter(x)\)。即，\(\Phi(x')\leq \Phi(x)\)。
因此，唯一勢能可能增加的點就是 \(y\)。而 \(y\) 的勢能最多增加 \(\alpha(n)\)。因此，可得 \(union\) 操作均攤後的時間複雜度為 \(\Theta(\alpha(n))\)。
find(a) 操作
如果查找路徑包含 \(\Theta(s)\) 個節點，顯然其查找的時間複雜度是 \(\Theta(s)\)。如果由於查找操作，沒有節點的勢能增加，且至少有 \(s-\alpha(n)\) 個節點的勢能至少減少 \(1\)，就可以證明 \(find(a)\) 操作的時間複雜度為 \(\Theta(\alpha(n))\)。為了避免混淆，這裏用 \(a\) 作為參數，而出現的 \(x\) 都是泛指某一個並查集內的結點。
首先證明沒有節點的勢能增加。很顯然，我們在上面證明過所有非根節點的勢能不增，而根節點的 \(rnk\) 沒有改變，所以沒有節點的勢能增加。
接下來證明至少有 \(s-\alpha(n)\) 個節點的勢能至少減少 \(1\)。我們上面證明過了，如果 \(level(x)\) 或者 \(iter(x)\) 有改變的話，它們的勢能至少減少 \(1\)。所以，只需要證明至少有 \(s-\alpha(n)\) 個節點的 \(level(x)\) 或者 \(iter(x)\) 有改變即可。
回憶一下非根節點勢能的定義，\(\Phi(x)=(\alpha(n)-level(x))\times rnk(x)-iter(x)\)，而 \(level(x)\) 和 \(iter(x)\) 是使 \(rnk(fa(x))\geq A_{level(x)}^{iter(x)}(rnk(x))\) 的最大數。
所以，如果 \(root_x\) 代表 \(x\) 所處的樹的根節點，只需要證明 \(rnk(root_x)\geq A_{level(x)}^{iter(x)+1}(rnk(x))\) 就好了。根據 \(A_k^i\) 的定義，\(A_{level(x)}^{iter(x)+1}(rnk(x))=A_{level(x)}(A_{level(x)}^{iter(x)}(rnk(x)))\)。
注意，我們可能會用 \(k(x)\) 代表 \(level(x)\)，\(i(x)\) 代表 \(iter(x)\) 以避免式子過於冗長。這裏，就是 \(rnk(root_x)\geq A_{k(x)}(A_{k(x)}^{i(x)}(x))\)。
當你看到這的時候，可能會有一種「這啥玩意」的感覺。這意味着你可能需要多看幾遍，或者跳過一些內容以後再看。
這裏，我們需要一個外接的 \(A_{k(x)}\)，意味着我們可能需要再找一個點 \(y\)。令 \(y\) 是搜索路徑上在 \(x\) 之後的滿足 \(k(y)=k(x)\) 的點，這裏「搜索路徑之後」相當於「是 \(x\) 的祖先」。顯然，不是每一個 \(x\) 都有這樣一個 \(y\)。很容易證明，沒有這樣的 \(y\) 的 \(x\) 不超過 \(\alpha(n)-2\) 個。因為只有每個 \(k\) 的最後一個 \(x\) 和 \(a\) 以及 \(root_a\) 沒有這樣的 \(y\)。
我們再強調一遍 \(fa(x)\) 指的是路徑壓縮 之前 \(x\) 的父節點，路徑壓縮 之後 \(x\) 的父節點一律用 \(root_x\) 表示。對於每個存在 \(y\) 的 \(x\)，總是有 \(rnk(y)\geq rnk(fa(x))\)。同時，我們有 \(rnk(fa(x))\geq A_{k(x)}^{i(x)}(rnk(x))\)。由於 \(k(x)=k(y)\)，我們用 \(k\) 來統稱，即，\(rnk(fa(x))\geq A_k^{i(x)}(rnk(x))\)。我們需要造一個 \(A_k\) 出來，所以我們可以不關注 \(iter(y)\) 的值，直接使用弱化版的 \(rnk(fa(y))\geq A_k(rnk(y))\)。
如果我們將不等式組合起來，神奇的事情就發生了。我們發現，\(rnk(fa(y))\geq A_k^{i(x)+1}(rnk(x))\)。也就是説，為了從 \(rnk(x)\) 迭代到 \(rnk(fa(y))\)，至少可以迭代 \(A_k\) 不少於 \(i(x)+1\) 次而不超過 \(rnk(fa(y))\)。
顯然，有 \(rnk(root_y)\geq rnk(fa(y))\)，且 \(rnk(x)\) 在路徑壓縮時不變。因此，我們可以得到 \(rnk(root_x)\geq A_k^{i(x)+1}(rnk(x))\)，也就是説 \(iter(x)\) 的值至少增加 1，如果 \(rnk(x)\) 沒有增加，一定是 \(level(x)\) 增加了。
所以，\(\Phi(x)\) 至少減少了 1。由於這樣的 \(x\) 節點至少有 \(s-\alpha(n)-2\) 個，所以最後 \(\Phi(S)\) 至少減少了 \(s-\alpha(n)-2\)，均攤後的時間複雜度即為 \(\Theta(\alpha(n)+2)=\Theta(\alpha(n))\)。
為何並查集會被卡
這個問題也就是問，如果我們不按秩合併，會有哪些性質被破壞，導致並查集的時間複雜度不能保證為 \(\Theta(m\alpha(n))\)。
如果我們在合併的時候，\(rnk\) 較大的合併到了 \(rnk\) 較小的節點上面，我們就將那個 \(rnk\) 較小的節點的 \(rnk\) 值設為另一個節點的 \(rnk\) 值加一。這樣，我們就能保證 \(rnk(fa(x))\geq rnk(x)+1\)，從而不會出現類似於滿地 compile error 一樣的性質不符合。
顯然，如果這樣子的話，我們破壞的就是 \(union(x,y)\) 函數「y 的勢能最多增加 \(\alpha(n)\)」這一句。
存在一個能使路徑壓縮並查集時間複雜度降至 \(\Omega(m\log_{1+\frac{m}{n}}n)\) 的結構，定義如下：
二項樹（實際上和一般的二項樹不太一樣），其中 j 是常數，\(T_k\) 為一個 \(T_{k-1}\) 加上一個 \(T_{k-j}\) 作為根節點的兒子。
邊界條件，\(T_1\) 到 \(T_j\) 都是一個單獨的點。
令 \(rnk(T_k)=r_k\)，這裏我們有 \(r_k=(k-1)/j\)（證明略）。每輪操作，我們將它接到一個單節點上，然後查詢底部的 \(j\) 個節點。也就是説，我們接到單節點上的時候，單節點的勢能提高了 \((k-1)/j+1\)。在 \(j=\lfloor\frac{m}{n}\rfloor\)，\(i=\lfloor\log_{j+1}\frac{n}{2}\rfloor\)，\(k=ij\) 的時候，勢能增加量為：
變換一下，去掉所有的取整符號，就可以得出，勢能增加量 \(\geq \alpha(n)\times(\log_{1+\frac{m}{n}}n-\frac{n}{m})\)，m 次操作就是 \(\Omega(m\log_{1+\frac{m}{n}}n-n)=\Omega(m\log_{1+\frac{m}{n}}n)\)。
關於啓發式合併
由於按秩合併比啓發式合併難寫，所以很多 dalao 會選擇使用啓發式合併來寫並查集。具體來説，則是對每個根都維護一個 \(size(x)\)，每次將 \(size\) 小的合併到大的上面。
所以，啓發式合併會不會被卡？
首先，可以從秩參與證明的性質來説明。如果 \(size\) 可以代替 \(rnk\) 的地位，則可以使用啓發式合併。快速總結一下，秩參與證明的性質有以下三條：
- 每次合併，最多有一個節點的秩上升，而且最多上升 1。
- 總有 \(rnk(fa(x))\geq rnk(x)+1\)。
- 節點的秩不減。
關於第二條和第三條，\(siz\) 顯然滿足，然而第一條不滿足，如果將 \(x\) 合併到 \(y\) 上面，則 \(siz(y)\) 會增大 \(siz(x)\) 那麼多。
所以，可以考慮使用 \(\log_2 siz(x)\) 代替 \(rnk(x)\)。
關於第一條性質，由於節點的 \(siz\) 最多翻倍，所以 \(\log_2 siz(x)\) 最多上升 1。關於第二三條性質，結論較為顯然，這裏略去證明。
所以説，如果不想寫按秩合併，就寫啓發式合併好了，時間複雜度仍舊是 \(\Theta(m\alpha(n))\)。
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：orzAtalod
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用