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

Question

Сегодня я обсуждал с кем-то алгоритм минимального связующего дерева Крускала из-за страницы 13 из этого слайда .

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

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

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

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

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

Answer 2

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

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 вы создаете локальный локатор, который никогда не выходит за пределы функции.Это не похоже, что это делает что-нибудь.И не ясно, каково ваше намерение в приложении.Возможно, вы захотите отредактировать и уточнить ваш подход.