Взвешенное быстрое объединение с алгоритмом сжатия пути: анализ временной сложности

Я изучаю алгоритм взвешенного быстрого объединения со сжатием пути для структуры объединения / поиска. Сайт edu в Принстоне подробно объяснил алгоритм. А вот реализация в Java:

public class WQUPC {
  private int[] id;
  private int[] sz;
  public WQUPC(int N) {
    id = new int[N];
    sz = new int[N];
    for (int i = 0; i < N; i++) {
      id[i] = i;
      sz[i] = 1;
    }
  }

  int root(int i) {
    while (i != id[i]) {
      id[i] = id[id[i]];
      i = id[i];
    }
    return i;
  }

  boolean connected(int p, int q) { return root(p) == root(q); }

  void union(int p, int q) {
    int i = root(p);
    int j = root(q);
    if (sz[i] < sz[j]) {
      id[i] = j;
      sz[j] += sz[i];
    } else {
      id[j] = i;
      sz[i] += sz[j];
    }
  }
}

Но так же, как сайт упоминает о его производительности:

Теорема. Начиная с пустой структуры данных, любая последовательность операций M union и find для N объектов занимает O(N + M lg* N) времени.

• Доказательство очень сложно.

• Но алгоритм все еще прост!

Но мне все еще интересно, как получается итеративный логарифм lg*n. Как это происходит? Может кто-то доказать это или просто объяснить это интуитивно?

Источник

2 ответа

Решение

Начнем с того, что в вашем вопросе есть небольшая ошибка: сложность только с сжатием пути составляет всего O (m log (n)) (без повторного журнала). См., Например, упражнение 21-4.4 в разделе Введение в алгоритмы. На самом деле, вы блокируете

    if (sz[i] < sz[j]) {
      id[i] = j;
      sz[j] += sz[i];
    } else {
      id[j] = i;
      sz[i] += sz[j];
    }

делает союз по рангу.

Тем не менее, при объединении по рангу и сжатию по пути используемое вами выражение может быть легко доказано (гораздо проще, чем обратное выражение Аккермана). Доказательство основано на трех моментах:

  1. На каждом пути корня листа ранг каждого узла увеличивается. На самом деле это основано на объединении по рангу, кстати, и это очень легко показать.

  2. Если корень дерева имеет ранг r, дерево имеет не менее 2 r узлов. Это можно показать по индукции.

Исходя из 2., можно показать

  1. Максимальное количество узлов с рангом r не более n / 2 r.

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

Источник

Насколько я помню, доказательство было связано с амортизацией стоимости сжатия пути по ряду поисков. Мелкий поиск дешев, и не требует больших затрат на сжатие пути; глубокий поиск обходится дорого для этого поиска и сжатия пути, но сжатие пути делает последующие поиски в среднем намного дешевле.

Источник
Другие вопросы по тегам