Занимаясь исправлением и дополнением статьи на емаксе, с удивлением обнаружил, что, оказывается, хорошо известная нам временная оценка, данная Тарьяном ещё в 1975 г., ставится под сомнение!

Самой адекватной критической статьёй мне показалась статья Zhang (2008 г.), см. ниже в конце списка.

Итак, хронология событий:

древность - известны разные реализации DSU, с различными эвристиками, по большей части с доказанным временем O(логарифма).

1973 г. - Hopcroft, Ullman - "Set-merging algomthms" - разработка сложного алгоритма DSU с асимптотикой О(итерированного логарифма).  

1975 г. - Tarjan - "Efficiency of a Good But Not Linear Set Union Algorithm" - впервые доказал, что давно известные всем эвристики сжатия пути и объединения по рангу работают за О(обратной функции Аккермана), причём доказал эту оценку как снизу, так и сверху.

1976 г. - Doyle, Rivest - "Linear Expected Time of a Simple Union-Find Algorithm" - предлагается версия DSU только со сжатием путей и показывается, что она работает за O(1) в среднем. Впрочем, как я понял, здесь анализируется случай, когда входные данные сами случайны.

1979 г. - Tarjan - "A Class of Algorithms which Require Nonlinear Time to Maintain Disjoint Sets" - помимо другого, содержит альтернативное доказательство того же факта (см. статья 1975 г.) про обратную функцию Аккермана.

1980 г. - Banachowsky - "A complement to Tarjan's result about the lower bound on the complexity of the set union problem" - указывается, что в доказательстве Тарьяна 1975 г. содержалась ошибка, и она исправлена (и факт ошибки был признан Тарьяном, см. статью 1984 г.).

1984 г. - Tarjan, Leeuwen - "Worst-Case Analysis of Set Union Algorithms" - ссылаются на статью 1975 г., упоминая при этом, что в доказательстве в ней была допущена ошибка, исправленная Баначовски (см. статья 1980 г.). В статье анализируются несколько различных алгоритмов DSU, но нижняя граница О(обратной функции Аккермана) здесь вроде бы не доказывается, а есть только лишь ссылки на статьи 1975 г. и 1979 г.

1985 г. - Yao - "On the expected performance of path compression algorithms" - доказательство того, что DSU работает за O(1) в среднем.

1989 г. - Fredman, Saks - "The cell probe complexity of dynamic data structures" - насколько я понял, описывается новый метод анализа асимптотики динамических структур данных. Этот метод применяется к доказательству нижней границы O(обратной функции Аккермана) для любого алгоритма DSU (теорема 5 в статье).

2005 г. - Wu, Otoo - "A Simpler Proof Of The Average Case Complexity Of Union-Find With Path Compression" - приводят альтернативную реализацию DSU, которая, как они доказывают, работает за O(1).

2008 г.(?) - Zhang - "The Union-Find Problem Is Linear" - предлагается доказательство того, что DSU на самом деле работает за O(1). В конце статьи приводится список ошибок (по мнению автора), содержащихся в доказательствах Тарьяна 1975 г. - 1979 г., а также ошибка в доказательстве Fredman-Saks 1989 г.

В общем, весьма запутанная ситуация. С одной стороны, доказательство Тарьяна за прошедшие 30 лет должно было быть прочёсано вдоль и поперёк. С другой - если после статьи 1975 г. в ней были обнаружены ошибки (см. Banachowsky 1980 г.), то до сих пор нельзя быть уверенным, что ошибок там больше нет.

Но, опять же, статьи китайских авторов не слишком внушают доверия. У меня не было сил углубляться в их доказательства, но вдруг они доказывают поведение DSU на случайных входных данных, вместо анализа худшего случая? Как, например, в статье Royle, Rivest 1976 г. (если я сам не ошибаюсь).

Интересно, кто-нибудь что-нибудь ещё слышал обо всём этом?