1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 31
Текст из файла (страница 31)
Тогда по лемме 4.2 и <е! !т (й) ( ~' пу2е((п!2~~в" т!е!) ( 1 + 9 + 4 + ' ' '1 ~( е е(е-!!+! П/27пги Ы ( П/Р (д). Наибольший штраф на узел с рангом из группы д)О не превосходит Р(а) — Р(а — 1). Поэтому наибольший штраф для узлов, ранги которых принадлежат группе д, ограничен числом и. Это утверждение, очевидно, верно и для у=О. Поскольку групп рангов не больше 0(п), то суммарный штраф, налагаемый на все узлы, не превосходит пб(п). Следовательно, общее время, требуемое для выполнения сп операций НАЙТИ, состоит из времени, не большего спб(п), на которое оштрафовано выполнение этих операций, и времени, не большего пб(п), на которое оштрафованы узлы. Таким образом, мы доказали следующую теорему. Теорема 4.4.
Пусть с — произвольная постоянная. Найдется другая постоянная с', эависжцая от с и такая, что алгоршпм 4.3 выполнит последовательность а иэ сп операций ОБЪЕДИНИТЬ и НАЙТИ на и элементах не более чем эа с'пб (и) единиц времени. Доказательство. Рассуждать, как выше. С) В качестве упражнения предлагаем показать, что если в последовательности о наряду с операциями ОБЪЕДИНИТЬ и НАЙТИ допускаются основные операции ВСТАВИТЬ и УДАЛИТЬ, то ее все равно можно выполнить за время 0(пб(п)). Неизвестно, точна ли оценка времени работы алгоритма 4.3, даваемая теоремой 4.4'). Однако в оставшейся части раздела мы докажем, поскольку это теоретически интересно, что время работы ал- ') По поводу сложности задачи, рассматриваемой в данном разделе, см.
работу Тарьина 1!9771.— Прим. лера!. ГЛ. 4. СТРУКТУРЫ ДАННЫХ ДЛЯ ЗАДАЧ С МНОЖЕСТВАМИ А' 4Г Рис. 4.2Н Результат операции ЧН. горитма 4.3 нелинейно по п. Для этого построим конкретную последовательность операций ОБЪЕДИНИТЬ и НАЙТИ, на которой алгоритм 4.3 работает нелинейное время. Удобно ввести новую операцию над деревьями, которую мы будем называть ЧАСТИЧНО НАЙТИ вЂ” сокращенно ЧН. Пусть Т— дерево, в котором узлы о, о„о„..., о„, в образуют путь из узла о к его предку ш (и не обязательно корень). Операция ЧН (о, ш) делает каждый из узлов п, о„о„..., о„, сыном узла н4. Мы будем говорить, что эта операция ЧН имеет длину т+1 (если о=и4, то длина равна 0).
На рис. 4,21,6 отражено влияние операции ЧН (о, и4) на дерево, приведенное на рис. 4.21,а. Пусть дана последовательность о операций ОБЪЕДИНИТЬ и НАЙТИ. Когда выполняется данная операция НАЙТИ из о, мы находим положение узла о в некотором дереве Т и идем по пути из о в корень 4а этого дерева. Теперь предположим, что выполняются только операции ОБЪЕДИНИТЬ из о, а операции НАЙТИ не выполняются. В результате получается некоторый лес )п. Действие данной операции НАЙТИ из о все еще можно уловить, если найти в Е положение узлов о и 4а, которые должна была использовать эта операция НАЙТИ, и затем выполнить ЧН (о, 4э). Заметим, что узел 4а может больше не быть корнем в Р. Для вывода нижней оценки времени работы алгоритма 4.3 исследуем его поведение на последовательности операций НАЙТИ, за которыми следуют операции ЧН. Зту последовательность можно заменить последовательностью операций ОБЪЕДИНИТЬ и НАЙТИ с тем же временем работы.
Из описанных ниже специальных де- гл, деввовидныв стьиктггы для з»д»чн овъвдинить — нляги Рис. 4,22. ггерево Т(»!. ревьев мы построим последовательности операций ОБЪЕДИНИТЬ и ЧН, на которых время работы алгоритма 4.3 более чем линейно. Определение. Для й)0 пусть Т(й) дерево, в котором 1) глубина каждого листа равна й 2) каждый узел высоты 6 имеет 2" сыновей, Й)1. Таким образом, корень дерева Т(й) имеет 2" сыновей, каждый из которых является корнем экземпляра дерева Т(й — 1). На рис. 4.22 изображено дерево Т(2). Лемма 4.4. Для каждого й~О можно построить дерево Т'(й), которое порождается некоторой последовательностью операций ОБЪЕДИНИТЬ и содержит в качестве подграфа дерево Т(й), причем по меньшей мере четверть узлов дерева Т'(й) являются листьями в Т (й). Д о к а з а т е л ь с т в о.
Доказательство проводится индукцией по й. Для й=О лемма тривиальна, ибо Т(0) состоит из одного узла. Чтобы построить Т'(й) для й)0, построим сначала 2"+1 экземпляров Т'(й — 1). Образуем дерево Т' (й)„выбрав один экземпляр Т'(й — 1) и затем влив в него один за другим каждый из оставшихся экземпляров.
Корень полученного дерева имеет (среди других) 2» сыновей, каждый из которых является корнем дерева Т'(!г — 1). Пусть Ф'(й) — общее число узлов в Т'(й) и Е(й) — число листьев в Т(й). Тогда М'(0) =1, йг'(й) =(2" +1) У'(й — 1) для й) 1 !. (0) = 1, Е (й) = 2»Е (й — 1) для й.=ь 1, откуда Ф' »! е 3 Г1 г ! 2-г для й "з 1. (4.3) Ц!2г+ ц г=г ГЛ. А СТРУКТУРЫ ДАННЫХ ДЛЯ ЗАДАЧ С МНОЖЕСТВАМИ Заметим, что для !«2 справедливо неравенство !п(1+2 ')~2 ~, поэтому А Х Ф (4.4) Комбинируя (4.3) с (4.4), получаем Е(й) 2, 1 М'(Ц 3 4' — « — е-ч «-. Лемма доказана. П Мы будем строить последовательность операций ОБЪЕДИНИТЬ н ЧН, которая сначала даст дерево Т'(й), а затем выполнит ЧН на листьях подграфа Т(й).
Сначала покажем, что для каждого 1= О найдется такое число й, что можно выполнить ЧН длины 1 последовательно на каждом листе дерева Т(й). Определение. Пусть 0(с, 1, й) — такое наименьшее значение й, что если заменить каждое поддерево в Т(й) с корнем высоты й любым деревом, имеющим 1 листьев н высоту не меньше 1, то на каждом листе полученного дерева можно будет выполнить ЧН длины с. Лемма 4.5.
Значение О(с, 1, й) определено (т. е. «онечно) для всех с, 1 и й, больших нуля. Д о к а з а тел ь с т в о. В доказательстве применяется двойная индукция. Мы хотим доказать наше утверждение индукцкей по с. Но для доказательства этого утверждения для с, исходя из истинности его для с — 1, надо провести индукцию по !. Базис, т. е. случай с=1, доказывается легко.
0(1, 1, й)=й для всех 1 и й, поскольку ЧН длины 1 не перемещает никаких узлов. Теперь, чтобы провести индукцию по с, предположим, что для всех 1 и й определено значение 0 (с — 1, 1, й). Мы должны показать, что Р (с, 1, й) определено для всех 1 и й, Это делается индукцией по 1. Для базиса индукции по 1 докажем, что О(с, 1, й) (О(с — 1, 2"+', й+1).
Заметим, что по определению числа О(с, 1, й) при 1 1 поддеревья в Т(й) с корнями высоты й заменяются деревьями с единственным листом. Пусть Н вЂ” множество узлов высоты й в дереве Т(й). Очевидно, что в этом преобразованном дереве каждый лист является подлинным потомком единственного элемента множества Н. Поэтому, если бы мы смогли выполнить операции ЧН длины с — 1 на всех элементах множества Н, то, конечно, смогли бы выполнить ЧН длины с на всех листьях.
СЕ ДРЕВОВИДНЫЕ СТРУКТУРЫ ДЛЯ ЗАДАЧИ ОБЪЕДИНИТЬ вЂ” НАЙТИ Пусть й=0(с — 1, 2"'", и+!). По предположению индукции для с число я существует. Все узлы высоты и+! в Т(я) имеют по 2"+' сыновей каждый, причем все сыновья принадлежат Н. Если удалить из Т(н) всех подлинных потомков узлов, входящих в О, то тем самым каждое поддерево с корнями на высоте 74+! заменится деревом высоты 1 с 2"+' листьями. По определению (л число Е=Р(с — 1, 2А4 4, й+!) достаточно велико, так что операции ЧН длины с — ! можно выполнить на всех листьях, т.
е. элементах множества Н. Теперь, чтобы завершить индукцию по с, осталось сделать шаг индукции по 1. В частности, покажем, что для 1) 1 О(с 1 Н)(о(с ! 2о<4,7-4.А774+о44,7-7,ьшз О(с 1 1 (т)) (4 5) Чтобы доказать неравенство (4.5), положим 17=О(с, 1 — 1, 17) и обозначим через 17' его правую часть, Нам надо найти способ заменить каждый узел высоты й в Т(н') деревом с 1 листьями, а затем на каждом листе выполнить операцию ЧН длины с.
Начнем с выполнения операций ЧН на 1 — 1 листьях каждого подставляемого дерева. По предположению индукции по 1 это сделать можно. Выполнив ЧН на 1 — 1 листьях, находим, что 1-й лист каждого подставляемого дерева теперь имеет отца, отличного от отца 1-го листа любого другого подставляемого дерева. Множество таких отцов обозначим через г. Если мы смогли выполнить операции ЧН длины с — 1 на этих отцах, то можем выполнить ЧН длины с на листьях.
Пусть 5 — поддерево с корнем высоты и в Т(е'). Легко проверить, что 5 содержит 2м" ч77 листьев в ТЯ). Поэтому после выполнения операций ЧН число узлов в 5, которые также принадлежат г, не превосходит 2мь 777'. Множество, оставшееся от 5, можно, следовательно, рассматривать как произвольное дерево с 2" <"+'>/7 листьями, которые принадлежат г. По предположению индукции для с и 1 неравенство (4.5) справедливо. С) Теорема 4.5. Временная сложность алгоритма 4.3 больше сп для любой постоянной с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
