set - アッカーマン関数が、素集合に使用される和集合検索アルゴリズムの償却された複雑さに関連しているのはなぜですか?

Question

なぜアッカーマン関数http://en.wikipedia.org/wiki/Ackermann_functionが素集合http://en.wikipedia.org/ wiki/Disjoint-set_data_structure ?

Tarjan のデータ構造に関する本の分析は、あまり直感的ではありません。

アルゴリズムの紹介でも調べましたが、厳密すぎて直感的ではないようです。

ご協力いただきありがとうございます！

Answer 1

素集合林に適用

ウィキペディアより

(find と union について) これら 2 つの手法は互いに補完し合います。一緒に適用すると、操作ごとの償却時間は O(α(n)) だけです。ここで、α(n) は関数 f(n) = A(n,n) の逆数であり、A は非常に急速に成長するアッカーマンです。関数。α(n) はこの関数の逆関数であるため、α(n) は、n のリモートで実用的なすべての値に対して 5 未満です。したがって、操作ごとの償却された実行時間は、実質的に小さな定数です。

なんでアッカーマン？

クラスカルアルゴリズムから

関数 lg*n

lg*n は非常にゆっくりと成長する関数であり、lg n よりもはるかに遅いことに注意してください。実際には、lg lg n、または lg n の任意の有限合成よりも遅いです。関数 f(n) = 2 ^2^2^…^2 の n 回の逆関数です。n >= 5 の場合、f(n) は宇宙の原子数よりも大きくなります。したがって、すべての意図と目的において、n の実際の値に対する f(n) の逆数は一定です。エンジニアの観点から見ると、Kruskal のアルゴリズムは O(e) で実行されます。もちろん、理論家の観点からは、O(e) の真の結果は依然として重要なブレークスルーであることに注意してください。 実際の最良の結果は、lg*n を A(p,n) の逆関数で置き換えることができることを示しているため、全体像は完全ではありません。ここで、A はアッカーマンの関数であり、爆発的に成長する関数です。アッカーマン関数の逆関数は lg*n に関連しており、より良い結果ですが、証明はさらに困難です。