1

Спасибо всем кто зашел сюда и уделил мне время.

Читаю Роберта Седжвика (с++) 2014, стр 31, Лемма 1.2.

Приведен пример решения задачи связности методом быстрого объединения.

for(i = p; i != id[i]; i = id[i]) ;
for(j = q; j != id[j]; j = id[j]) ;
if(i == j) continue;
id[i] = j;

С этим все ясно, далее он пишет о эффективности алгоритма:

Для M пар из N объектов, когда M > N, решение задачи связности алгоритмом быстрого объединения может потребовать выполнения более чем M N/2 инструкций.

Говорит он про пары M, в их число ведь входят правильные пары и не правильные? Те которые просто поступают на ввод?

Предположим, что пары вводятся в следующем порядке (1-2 2-3 3-4) итд. После ввода N-1 таких пар мы получим N объектов, принадлежащих к одному множеству,a сформированное алгоритмом быстрого объединения дерево представляет собой прямую линию, где объект N указывает на объект N-1, тот, в свою очередь - на объект N-2, тот на N-3 и тд. Чтобы выполнить операцию поиск для объекта N, программа должна перейти по N-1 указателям. Таким образом, среднее количество указателей, по которым выполняются переходы для первых N пар, равно (0+1+...(N-1))/N = (N-1)/2

Зачем он находит среднее арифмитическое?! Он ведь говорит что список построен (1-2 2-3 3-4) и тд, что бы пройти от начала до конца нужно N-1 раз пройти. Не понятно что он имеет введу "переходы для первых N пар"?

Теперь предположим, что все остальные пары связывают объект N с каким либо другим объектом. Чтобы выполнить операцию поиск для каждой из этих пар требуется перейти, по меньшей мере, по N-1 указателям. Общий итог для M операций поиск при такой последовательности вводимых пар определенно больше MN/2

Что он имеет введу "все остальные пары", неправильные пары в вводе? Как он вывел MN/2?

Возможно я где то сглупил, помогите пожалуйста.

2 ответа 2

2

Говорит он про пары M, в их число ведь входят правильные пары и не правильные? Те которые просто поступают на ввод?

Что такое, в вашем понимании, "неправильные" пары? Нет никакого разделения пар на правильные и нет, есть только вершины и ребра графа.

Зачем он находит среднее арифмитическое?! Он ведь говорит что список построен (1-2 2-3 3-4) и тд, что бы пройти от начала до конца нужно N-1 раз пройти.

Речь идет, напомню, про оценку времени. Программа выполняет N операций объединения - при этом каждая операция занимает какое-то свое время. Чтобы можно было что-то сказать про время выполнения операции в целом - надо эти значения усреднить. Затем и среднее арифметическое.

Не понятно что он имеет введу "переходы для первых N пар"? Что он имеет введу "все остальные пары", неправильные пары в вводе? Как он вывел MN/2?

Автор рассматривает такую последовательность пар на входе алгоритма в качестве примера "плохой" последовательности:

  1. сначала идет N-1 пара - (1,2), (2,3), ..., (N-1, N);
  2. потом идет M-N+1 пара вида (*, N).

Каждая пара обрабатывается приведенным вами алгоритмом. "Переход" - это итерация одного из циклов for в первых двух строках.

Так, для пары (4,5) из первого блока придется пройти 4-3-2-1 (5 пока еще ни с кем не связана), всего 3 перехода.

Для пары (4, N) из второго блока придется пройти сначала 4-3-2-1, а потом еще N-(N-1)-...-4-3-2-1, всего N+2 перехода.

10
  • Правильные/неправильные - я так подумал когда прочел "Для M пар из N объектов, когда M > N", он написал ранее что "алгоритм решения задачи связности никогда не выводит более N-1 пар, поскольку как только он выведет N-1 пару, любая встретившаяся после этого пара, будет уже связная" уже связная - неправильная, "if(i==j) continue;" Cначала N-1 пара - (1,2), (2,3), ..., (N-1, N), потом все "неправильные" связи.
    – uskabuska
    Commented 10 июн. 2015 в 13:26
  • Зачем находить среднее значение? Укажите пожалуйста, где операции разные? ;c
    – uskabuska
    Commented 10 июн. 2015 в 13:27
  • 1
    Для пары (1,2) не выполняется никаких переходов, для пары (2,3) делается 1 переход, потом 2, 3 и т.д. до N-1 перехода. Commented 10 июн. 2015 в 13:30
  • Где 1 переход? savepic.ru/7332262.png Может вы имели введу "синхронизацию" количества итераций между 2мя циклами? Поэтому среднее находится?
    – uskabuska
    Commented 10 июн. 2015 в 14:00
  • Но ведь в таком примере нет разницы между ними. (посмотрите картинку, пожалуйста)
    – uskabuska
    Commented 10 июн. 2015 в 14:09
1

Он просто сначала рассмотрел группу первых X union-ов, а затем - группу других Y. Из свойства первой группу он вывел, что число операций для каждого вызова union во второй группе ограничено снизу числом (X - 1), отсюда получил как минимум Y(X - 1) операций. Просто небольшая вольность языка.

UPD: из второго четвертого издания:

Again, suppose that we use quick-union for the dynamic connectivity problem and wind up with a single component. An immediate implication of PROPOSITION G is that the running time is quadratic, in the worst case. Suppose that the input pairs come in the order 0-1, then 0-2, then 0-3, and o forth. After N - 1 such pairs, we have N sites all in the same set, and the tree that is formed by the quick-union algorithm has height N - 1, with 0 linking to 1, which links to 2, which links to 3, and so forth (see the diagram on the facing page). By PROPOSITION G, the number of array accesses for the union() operation for the pair 0 i is exactly 2i + 3 (site 0 is at depth i and site i at depth 0). Thus, the total number of array accesses for the find() operations for these pairs is (3 + 5 + 7 + … + 2N + 1) ~ N^2.

Видимо, действительно в первом издании было плохо понятно, поэтому во втором четвертом пример полностью переработали :) Могу лишь посоветовать заказать второе издание, это признанный шедевр.

2
  • В интернете нашел только 2014 года и 2011 года, а какое у вас издание?
    – uskabuska
    Commented 10 июн. 2015 в 14:50
  • 1
    @uskabuska четвертое издание, 2014 Commented 10 июн. 2015 в 15:47

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.