O(1) Структура данных "Создать, найти, объединить в непересекающиеся множества"

Question

Сегодня у меня была дискуссия с кем-то об алгоритме Kruskal Minimum Spanning Tree из-за страницы 13 этого слайда.

Автор презентации сказал, что если мы реализуем непересекающиеся множества, используя (дважды) связанный список, производительность для Make и Find будет O(1) и O(1) соответственно. Время операции Union(u,v) равно min (nu, nv), где nu и nv - размеры наборов, хранящих u и v.

Я сказал, что мы можем улучшить время, в течение которого Union(u,v) будет равно O(1), сделав указатель представления каждого члена, указывающий локатор, который содержит указатель на реальное представление множества.

В Java структура данных будет выглядеть так:

class DisjointSet {
    LinkedList<Vertex> list = new LinkedList<Vertex>(); // for holding the members, we might need it for print

    static Member makeSet(Vertex v) {
        Member m = new Member();

        DisjointSet set = new DisjointSet();
        m.set = set;
        set.list.add(m);

        m.vertex = v;

        Locator loc = new Locator();
        loc.representation = m;
        m.locator = loc;

        return m;
    }
}

class Member {
    DisjointSet set;
    Locator locator;
    Vertex vertex;

    Member find() {
        return locator.representation;
    }

    void union(Member u, Member v) { // assume nv is less than nu
        u.set.list.append(v.set.list); // hypothetical method, append a list in O(1)
        v.set = u.set;
        v.locator.representation = u.locator.representation;
    }

}

class Locator {
    Member representation;
}

Извините за минималистичный код. Если это можно сделать таким образом, то время выполнения для каждой непересекающейся операции набора (Make, Find, Union) будет O(1). Но тот, с кем я обсуждал, не видит улучшения. Я хотел бы узнать ваше мнение по этому поводу.

А также, какова самая быстрая производительность Find/Union в различных реализациях? Я не эксперт в области структуры данных, но благодаря быстрому просмотру в Интернете я обнаружил, что для этого не существует структуры данных или алгоритма с постоянным временем.

Answer 1

Моя интуиция согласна с вашим коллегой. Ты говоришь:

u.set.list.append(v.set.list); // hypothetical method, append a list in O(1)

Похоже, ваше намерение состоит в том, что объединение осуществляется через приложение. Но, чтобы внедрить Union, вам нужно будет удалить дубликаты, чтобы результат был набором. Так что я вижу алгоритм O(1) для фиксированного размера набора, например...

Int32 set1;
Int32 set2;

Int32 unionSets1And2 = set1 | set2;

Но это кажется мне обманом. Если вы делаете это для общих случаев N, я не вижу, как вы избегаете какой-либо формы итерации (или поиска хеша). И это сделало бы это O(n) (или в лучшем случае O(log n)).

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

Answer 2

Используя версию Терьяна структуры Union-Find (со сжатием пути и взвешенным по рангу объединением), последовательность m Finds и (n-1) смешанных объединений будет в O(m.α(m,n)), где α (m, n) - обратная функция Аккермана, которая для всех практических значений m и n имеет значение 4. Таким образом, это в основном означает, что Union-Find имеет амортизированные постоянные операции в худшем случае, но не совсем.

Насколько мне известно, невозможно получить лучшую теоретическую сложность, хотя улучшения привели к повышению практической эффективности.

Для особых случаев непересекающихся множеств, таких как те, которые используются в теории языка, было показано, что линейные (т.е. все в O(1)) адаптации возможны - по существу, путем группировки узлов вместе - но эти улучшения не могут быть переведено на общую проблему. С другой стороны спектра, несколько схожая основная идея была использована с большим успехом и изобретательностью для создания алгоритма O(n) для минимального остовного дерева (алгоритм Шазеля).

Таким образом, ваш код не может быть правильным. Ошибка - то, на что указал Морон: когда вы объединяете два набора, вы обновляете только "представление" опережения каждого списка, но не всех других элементов - одновременно допуская в функции поиска, что каждый элемент напрямую знает свое представление.