Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 135
Текст из файла (страница 135)
Для получения потенциала всего леса мы суммируем потенциалы его узлов: Фч — — 2'„фч(х), где Фч обозначает потенциал всего леса после выполнениЯ а операций. До выполнения первой операции лес пуст, и мы полагаем, что Фс = О. Потенциал Фч никогда не может стать отрицательным.
Значение Фч(х) зависит от того, является ли х корнем дерева после д-й операции, Если это так или если х. гапй = О, то фч(х) = о(п) х. гагй. Теперь предположим, что после д-й операции х не является корнем и что х. гапк > 1. Необходимо определить две вспомогательные функции от х до определения фч(х), Сначала определим Глава Л. Структуры данные длл ненересекающиксл множеств Вторая вспомогательная функция применима при х. татй > 1: !тег(х) = шах~в: х.р.таей > А„'„„, (х.тап)с)), т.е. функция !сег(х) представляет собой наибольшее количество итеративного применения функции А1, й ) к исходному рангу х, до того как мы получим значение, превышающее ранг родителя х.
Мы утверждаем, что при х. тап)с > 1 1 < Ыег(х) < х. тап)с, (21.2) в чем можно убедиться следующим образом. Мы имеем х.р. татй > А)„,1! )(х. тап)с) (согласно определению!етеЦх)) (1) = А„„„(х. татй), где последнее равенство следует из определения функциональной итерации. От- сюда вытекает, что !сег(х) > 1, и мы имеем А, „(х. ппй) = А)в„в)( )+1(х. татй) (по определению Аь(~)) 1е.
тена+1) > х.р.тап)т (по определению 1ече1(х)), откуда следует, что 11ег(х) < х.татй. Заметим, что, поскольку х.р.татй монотонно возрастает со временем, для того, чтобы значение !1ег(х) уменьшалось, значение!ете1(х) должно возрастать. Пока значение 1ече1(х) остается неизменным, значение !тег(х) должно либо увеличиваться, либо вообще не изменяться.
Имея описанные вспомогательные функции, мы можем определить потенциал узла х после д операций: а(п) ° х. тап)с, если х является корнем или х.татй = О, фв(х) = (а(п) — 1еуе1(х)) х.тап)с — 1сег(х), если х — не корень и х.тап)т > 1. Далее рассмотрим некоторые полезные свойства потенциалов узлов.
л ггв Для каждого узла х и для всех количеств операций д имеем О < фв(х) < а(п) х. тап)с . Доказательствоо. Если х является корнем или х.татй = О, то фв(х) а(п) х.таей по определению. Предположим теперь, что х не является корнем и что х. тап)с > 1. Мы получим нижнюю границу фв(х) путем максимизации 1еуе1(х) и !ьег(х). Согласно границе (21.1) 1ече1(х) < а(п) — 1, а согласно рч усы Ь границе (21.2) !1ег(х) < х.
тап)д. Таким образом, фд(х) = (а(п) — 1ече1(х)) х. тапй — !$ег(х) > (гд(п) — (а(п) — 1)) х.гап)д — х.гагй = х. гап!д — х. та~й =0 Аналогично мы получаем верхнюю границу фд(х) минимизацией !ече1(х) и !зег(х). В соответствии с границей (21.1) 1ече1(х) > О, а в соответствии с границей (21.2) !!ег(х) > 1. Таким образом, фд(х) < (а(п) — 0) х. тапа — 1 = о(п) х.
татй — 1 < гд(п) х.тагй . Следсвдвве 21. 9 Если узел х не является корнем и х. гап!д > О, то фд(х) < а(п) х. гапк. ° Изменения потенциала и амортизированная стоимость операций Теперь мы готовы к рассмотрению вопроса о влиянии операций над непересекающимися множествами на потенциалы узлов. Зная, как изменяется потенциал при той или иной операции, мы можем определить амортизированную стоимость каждой операции. Лемма 21.10 Пусть х — узел, не являющийся корнем, и предположим, что 9-я операция — либо 1.!!дк, либо Р!гдп-Бет. Тогда после выполнения 9-й операции фд(х) < фд-!(х) Более того, если х. тапа > 1 и из-за выполнения 9-й операции происходит изменение либо 1ече!(х), либо !$ег(х), то фд(х) < фд ! (х) — 1.
То есть потенциал х не может возрастать, и если он имеет положительное значение и либо 1ече1(х), либо !Фег(х) изменяется, то потенциал х уменьшается как минимум на 1. Двказавдельсвдвв. Поскольку х ие является корнем, 9-я операция ие изменяет х.гагй, и так как и не изменяется после первых и операций Маке-бет, гд(п) остается неизменной величиной. Следовательно, эти компоненты формулы функции потенциала х после выполнения 9-й операции не изменяются. Если х. тагй = О, то фд(х) = фд 1(х) = О. Теперь предположим, что х.
тапа > 1. Вспомним, что значение функции 1ече1(х) монотонно растет со временем. Если 9-я операция оставляет значение 1ече1(х) неизменным, то значение !Фег(х) либо возрастает, либо остается неизменным. Если н 1ече1(х), и !гег(х) не изменяются, то фд(х) = фд !(х). Если же значение 1ече!(х) не изменяется, а !Фег(х) возрастает, то последнее значение увеличивается как минимум на 1, так что фд(х) < фд-1(х) — 1 Глава 2Л Струющрт даннтл длл ненересенаюнеслсл множеств б!5 Наконец, если 9-я операция увеличивает 1ете1(х), то это увеличение составляет как минимум 1, так что значение члена (а(п) — !ече!(х)) х. гап(е уменьшается как минимум иа величину х.
гап)е. Так как значение 1ете1(х) возрастает, значение !гег(х) может уменьшаться, но в соответствии с границей (21.2) это уменьшение не может превышать х.гап)е — 1. Таким образом, увеличение потенциала, вызванное изменением значения !гег(х), меньше, чем уменьшение потенциала из-за изменения!ече!(х), так что мы можем заключить, что фч(х) < фв 1(х) — 1. ° Наши последние три леммы показывают, что амортизированиая стоимость каждой из операций Млкн-Бнт, Ьпчк и гпмнп-Бнт составляет 0(сг(п)). Вспомним, что согласно (17.2) амортизированиая стоимость каждой операции равна ее фактической стоимости плюс увеличение потенциала, вызванное ее выполнением. Лемма 21.11 Амортизированная стоимость каждой операции Млкн-Бит равна 0(1). Л 21.12 Амортизированная стоимость каждой операции Ь!мк равна 0(а(п)). Двказааеельсшвв. Предположим, что 9-й операцией является 1.пчк(х, у). Фактическая стоимость операции Ь!мк равна 0(1).
Без потери общности предположим, что Ь|мк делает у родительским узлом х. Для определения изменения потенциала из-за выполнения операции Ь!мк заметим, что множество узлов, потенциалы которых могут измениться, ограничено узлами х, у и дочерними узлами у непосредственно перед операцией. Мы покажем, что единственным узлом, потенциал которого может увеличиться в резутп; тате выполнения операции Ьпчк, является узел у, и это увеличение не превышает гл(п). Согласно лемме 21.10 потенциал любого узла, являющегося дочерним узлом у перед выполнением операции Ь|мк, не может увеличиться в результате выпол- нения этой операции. По определению фч(х) мы видим, что, поскольку узел х непосредственно пе- ред о-й операцией был корнем, фд 1(х) = ге(п) х. гап)е.
Если х. гап)е = О, то фч(х) = фч з(х) = О. В противном случае ф (х) ( ~(~) х. ~пlс = фч 1(х), (согласно следствию 21.9) так что потенциал х уменьшается. Даказагаельсаева. Предположим, что д-й операцией является Млкн-Бнт(х). Эта операция создает узел х с рангом О, так что фч(х) = О. Никакие иные ранги и потенциалы не изменяются, так что Фо = Ф„ь То, что фактическая стоимость операции Маке-Бет равна 0(1), завершает доказательство.
Часть К Слажные структуры данны б!б Посюльку у непосредственно перед выполнением операции Ь//цк был юрием, фц г(у) = а(п) . у. гап/с. Операция Ь!йк оставляет у корнем и либо оставляет ранг у неизменным, либо увеличивает его на 1. Следовательно, либо фц(у) = фц з(у), либо фц(у) = фц т(у) + а(п). Таким образом, увеличение потенциала вследствие операции Ьгмк не превышает а(п), и амортизированная стоимость операции Ьгьтк равна 0(1) + а(п) = 0(а(п)). Лемма 21. 13 Амортизированная стоимость каждой операции Р/ьт/з-Бит равна 0(а(п)).
х.р. тптй > А1ь' "(*11(х. татй) у.р.гатй > Аь(у.тап/с) у. гатй > х.р. тапИ (по определению 1сег(х)), (по определению 1ече1(у)), (согласно следствию 21.5 и поскольку у следует за х на пути поиска) . Объединив приведенные неравенства и обозначив через т значение 1сег(х) перед сжатием пути, получаем у. р, тапИ > Аь(у. гапИ) > Аь(х.р. тап/с) > Аь(Аь(' Ц 0(х.гатй)) = Аь('~ т(х.гап/с) . (поскольку Аь(~) строго возрастающая) Доказательство. Предположим, что д-й операцией является Ртнгз-Кит и что путь поиска содержит в узлов. Фактическая стоимость операции Рпцп-Бит составляет 0(в). Покажем, что отсутствуют узлы, потенциал которых возрастает вследствие операции Ртмгт-Бит, и что как минимум у шах(0, в — (а(п) + 2)) узлов иа пути поиска потенциал уменьшается по меньшей мере на 1.
Чтобы увидеть отсутствие узлов с возрастающим потенциалом, обратимся к лемме 2!.10 для всех узлов, не являющихся корнем. Если же узел х является корнем, то его потенциал равен а(п) х, тапИ и остается неизменным. Теперь покажем, что потенциал как минимум шах(0, в — (а(п) + 2)) узлов уменьшается по меньшей мере на 1. Пусть х — узел на пути поиска, таюй, что х. тап/с > О, и за х на пути поиска следует другой узел у, не являющийся корнем, где непосредственно перед выполнением операции Рпцгт-Бит 1ече1(у) = 1ече1(х) (узел у не обязательно следует непосредственно за х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
