反阿克曼界（inverse-Ackermann bound）
/ AK-er-man /
阿克曼函數是個著名的例子，它快到幾乎難以想像——比任何指數塔都快——靠把遞迴套在遞迴裡。因此它的反函數，寫成 alpha(n)，慢到幾乎難以想像：它是你要把一個瘋狂快速成長的操作施用幾次，才能從一個小數爬到 n。對你在電腦裡所能儲存的任何 n——其實對遠大於宇宙原子數的 n——alpha(n) 至多 4 或 5。它技術上不是常數，但實質上就是常數。
這個函數正是並查集在你「同時」使用路徑壓縮與按秩合併時，每個操作的確切攤還成本。塔揚（Tarjan）證明對 n 個元素的 m 個操作序列總共跑 O(m * alpha(n)) 時間，所以每個操作攤還成 O(alpha(n))。這個證明是基礎演算法中最精巧的之一：它依節點的秩與其父的秩如何比較，把節點分配到不同「層級」，並把每次 Find 的工作或歸到操作本身、或歸到被升到更高層級的節點，說明每個節點每層級只能被計費有限次，而層級只有 alpha(n) 個。結論是這個自我改善的結構把罕見的昂貴操作回報得如此徹底，使平均本質上是常數。還有一個相符的下界：沒有任何以指標為基礎的並查集能勝過 alpha(n) 攤還，所以這不只是已知最佳的界，而是可證明為最優的。
反阿克曼界正是為何並查集在實務上被當作「實質常數時間」——克魯斯卡爾最小生成樹、連通性查詢，以及數十種其他演算法都倚賴它。誠實的表述：alpha(n) 作為函數確實不是 O(1)（它確會趨於無窮，只是慢如冰川），而且這界是攤還的，所以單一次 Find 在壓平一條長路徑時仍可能比 alpha(n) 久。但對任何真實輸入，alpha(n) 與常數之分純屬學術——你永遠不會看到 alpha(n) 超過 5。
要體會 alpha 成長之慢：一個相關的慢函數，迭代對數 log*(n)，需要約 5 次套用 log 才能把 2^65536 降到 1 以下，而 alpha(n) 比 log*(n) 還慢。所以對一百萬個元素做一百萬個操作，每個攤還約 4 或 5 單位——在任何真實程式中與常數無法區別。
對你可能遇到的任何 n，alpha(n) 至多 4 或 5——實質上是常數，雖然字面上不是 O(1)。
alpha(n) 字面上不是常數——它確會增長到無窮，而且這界是攤還的。但它對以指標為基礎的並查集可證明為最優，且在真實輸入上從不超過約 5，所以在實務上把它當常數是公平的，雖在嚴格極限下並不正確。