Структуры данных и модели вычислений
Нахождение суммарной оценки времени выполнения
Нахождение суммарной оценки времени выполнения m операций СЛИТЬ. Введем определение. Узел назовем тяжелым, если количество узлов в его правом поддереве строго больше, чем в левом. Остальные узлы назовем легкими.
Определим потенциал коллекции куч как общее количество содержащихся в ней тяжелых узлов. Пусть — потенциал коллекции после выполнения -й операции.
Утверждение.
Время выполнения операций СЛИТЬ, примененных к коллекции, состоящей из куч с нулевым потенциалом, является величиной , где
— общее количество узлов в коллекции.
Доказательство.
Пусть -я операция заключается в слиянии куч и в результирующую кучу . Пусть перед ее выполнением и — количества тяжелых узлов в правых путях куч и соответственно,
и — количества легких узлов в этих путях, ,
— количества тяжелых узлов в остальных частях куч.
Время выполнения этой операции с точностью до постоянного множителя оценивается сверху величиной .
Подсчитаем изменение потенциала при ее выполнении. Имеем
По завершении этой операции тяжелые узлы правых путей становятся легкими, их количество равно . Легкие узлы правых путей могут как стать тяжелыми, так и остаться легкими, их будет не более штук, а количества тяжелых узлов в остальной части обоих деревьев не изменились. Следовательно, количество
тяжелых узлов после выполнения операции удовлетворяет неравенству
Таким образом, получаем изменение потенциала
и, следовательно,
Из определения легкого узла следует, что количество легких узлов в куче не превосходит логарифма количества узлов в этой куче.
Следовательно, где , а — общее количество узлов в исходных кучах.
Суммируя левую и правую части последнего неравенства по , получаем, что величина
с точностью до постоянного множителя оценивается сверху величиной, пропорциональной , то есть принадлежит .
Величина является амортизационной оценкой времени выполнения операции СЛИТЬ, то есть величиной .
Замечание.
Вначале коллекция, состоящая из куч, к которым применяются операций СЛИТЬ, может иметь произвольное количество узлов, в сумме равное .Важно, чтобы потенциал каждой из них, следовательно, и суммарный потенциал был равен нулю, то есть кучи не должны первоначально иметь тяжелых узлов.
Это могут быть, например, кучи, целиком являющиеся левыми путями. Крайний случай — это куча высоты с минимальным количеством узлов, не имеющая тяжелых узлов, а также это могут быть кучи с заполненным последним уровнем узлов. Другой крайний случай — это куча высоты
с максимальным количеством узлов, не имеющая тяжелых узлов. Остальные варианты являются промежуточными.
Особое значение имеет случай, когда каждая из начальных куч состоит из единственного узла.
Итак, для всех коллекций таких куч амортизационное время выполнения одной операции СЛИТЬ является величиной , где
— общее количество их узлов.
