Почему функция Аккермана связана с амортизированной сложностью алгоритма поиска по объединению, используемого для непересекающихся множеств?

Кто-нибудь может дать мне интуитивное объяснение, почему функция Аккермана http: //en.wikipedia.org / wiki / Ackermann_function связана с амортизированной сложностью алгоритма поиска объединения, используемого для непересекающихся множеств http://en.wikipedia.org/wiki/Disjoint-set_data_structure ?

Анализ в книге Тарьяна о структуре данных не очень интуитивно понятен.

Я также искал это во Введении в алгоритмы, но он также кажется слишком строгим и неинтуитивным.

Спасибо за вашу помощь!

8
задан Tianyang Li 14 June 2011 в 12:52
поделиться