Амортизированное время на операцию с использованием непересекающихся множеств

Question

Я случайно прочитал в Википедии, что время амортизации одной операции на непересекающемся множестве (объединение двух элементов, поиск родительского элемента для определенного элемента) равно O (a (n)), где a (n) - обратная функция Аккермана , который растет очень быстро.

Может кто-нибудь объяснить, почему это так?

Answer 1

Ну, это было бы довольно сложно объяснить, потому что это не так. Это не обратная функция Аккермана, которая растет как ракета на стероидах, а обратная Аккерманна растет очень медленно.

Это дает вам теоретическое обоснование.

Answer 2

Доказательство этого факта содержится в Введение в алгоритмы . Кажется, это довольно популярное чтение, и в вашей городской или школьной библиотеке может быть копия. Я также видел копии, плавающие в Интернете, но законность их, вероятно, сомнительна.

РЕДАКТИРОВАТЬ: блок доказательства представляется читабельным в Google Книгах.

Answer 3

Ну, на странице Википедии есть цитата. Если вам это интересно, проверьте это. Если вы учитесь в колледже, это должно быть легко, а если нет, просто найдите ближайший колледж и используйте его библиотеку (им все равно, если вы не студент).