Спасибо всем кто зашел сюда и уделил мне время.
Читаю Роберта Седжвика (с++) 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?
Возможно я где то сглупил, помогите пожалуйста.