Почему функция Аккермана связана с амортизируемой сложностью алгоритма поиска объединения, используемого для непересекающихся множеств?
Кто-нибудь может дать мне интуитивное объяснение того, почему функция Аккермана http://en.wikipedia.org/wiki/Ackermann_function связана с амортизируемой сложностью алгоритма поиска объединения, используемого для непересекающихся множеств http://en.wikipedia.org/wiki/Disjoint-set_data_structure?
Анализ в книге структуры данных Тарьяна не очень интуитивен.
Я также посмотрел его в разделе Введение в алгоритмы, но он также кажется слишком строгим и неинтуитивным.
Спасибо за вашу помощь!
1 ответ
Применяется к непересекающимся лесам
из Википедии
(о находке и объединении) Эти две техники дополняют друг друга; При совместном использовании амортизированное время на операцию составляет всего O(α(n)), где α (n) - обратная функция f(n) = A(n,n), а A - чрезвычайно быстро растущий Аккерманн функция. Поскольку α (n) является обратной к этой функции, α(n) меньше 5 для всех отдаленных практических значений n. Таким образом, амортизированное время работы на операцию фактически является небольшой константой.
Так почему Акерман?
Функция LG * N
Обратите внимание, что lg*n - очень медленно растущая функция, намного медленнее, чем lg n. На самом деле медленнее, чем lg lg n или любой конечный состав lg n. Это обратная функция f(n) = 2 ^2^2^…^2, n раз. При n >= 5 f (n) больше, чем число атомов во вселенной. Следовательно, для всех намерений и целей обратное значение f (n) для любого реального значения n является постоянным. С точки зрения инженера, алгоритм Крускала работает в O(e). Заметим, конечно, что с точки зрения теоретика, истинный результат O (e) все равно будет значительным прорывом. Вся картина не полная, потому что фактический лучший результат показывает, что lg*n может быть заменено на инверсию A(p,n), где A - функция Аккермана, функция, которая взрывно растет. Обратная функция Аккермана связана с lg*n и является более хорошим результатом, но доказательство еще сложнее.