Первая страница / Теория / Построение и анализ алгоритмов /

Применения амортизационного анализа

Голосование: 8, 2

Введение

Необходимость в тщательном анализе времени исполнения алгоритмов, а также используемой при этом памяти, резко возросла с развитием компьютерной техники и объемов решаемых задач. Очень часто такие оценки можно получить, исходя из элементарных соображений. В данной статье речь пойдет о достаточно распространенном на сегодняшний день подходе к анализу алгоритмов, называемом амортизационным анализом.

Уже давно при решении множества математических задач применялись методы, в которых можно угадать черты современного анализа алгоритмов. В математике при доказательстве конечности некоторого процесса одним из классических является прием выделения некоторой величины, монотонно изменяющейся в ходе этого процесса (такие величины называют полуинвариантами). Тогда если набор значений, которые может принимать полуинвариант, конечен, то и процесс обязательно закончится через конечное число шагов (так как никакое значение не может быть получено больше одного раза).

Если разбить алгоритм на более маленькие шаги и оценить, сколько времени требуется вычислителю на их исполнение, а так же найти зависимость количества шагов каждого типа от размера решаемой задачи, будет получена общая оценка времени работы всего алгоритма. Очевидно в частности, что время, прошедшее с начала исполнения алгоритма, является тривиальным полуинвариантом вычислительного процесса. Большую пользу могут дать такие полуинварианты, как количество необработанных элементов или значение максимума, найденного на данный момент.

Однако часто оказывается, что время, необходимое для исполнения совокупности одинаковых шагов, может существенно отличаться от произведения их количества на наибольшее время исполнения одного шага в худшем случае. Возникает необходимость для более детального изучения того, что происходит на каждом шаге, и как одни шаги могут влиять на другие. Этим и занимается амортизационный анализ.

Для того, чтобы получить основные определения, а также познакомиться с некоторыми классическими примерами, читателю предлагается изучить соответствующий раздел в фундаментальном учебнике [1], или статью [2].

Перейдем к рассмотрению некоторых других примеров использования амортизационного анализа.

Система непересекающихся множеств

С применениями амортизационного анализа чаще всего приходится сталкиваться при оценке времени, требуемого для выполнения последовательности действий различными структурами данных. При этом очень часто можно столкнуться с такими оценками, которые на первый взгляд кажутся недостижимыми.

Система непересекающихся множеств — структура данных, которая хранит разбиение элементов некоторого набора на множества и поддерживает две основные операции:

  1. нахождение множества, которому принадлежит данный элемент;
  2. объединение двух множеств в одно.

При этом амортизированное время выполнения этих действий оказывается столь малым, что в большинстве решаемых задач его можно считать ограниченным небольшой константой. Здесь приводится оценка через итерированный логарифм размера множества. Итерированный логарифм числа m (для него принято обозначение log*m) равен числу раз, которое нужно взять логарифм от числа m, чтобы получилось число, меньшее 1. Более сильная оценка через так называемую обратную функцию Аккермана α(mn) получается похожим способом, но требует построения сложных конструкций и громоздких математических выкладок.

Принцип работы

Сначала опишем принцип работы системы непересекающихся множеств. Пусть в каждый момент имеется лес корневых деревьев, в котором все ребра ориентированы по направлению к корням. При этом вершины соответствуют элементам набора, а деревья ассоциируются с множествами. Тогда множество, в котором находится элемент, однозначно задается корнем соответствующего дерева, а объединить два множества можно, соединив два дерева.

В дальнейшем будем отождествлять элементы с соответствующими вершинами, а множества — с корнями деревьев. Следовательно, нахождение множества, содержащего элемент, сводится к нахождению представителя этого множества — корня соответствующего дерева. В начальном состоянии каждый элемент принадлежит собственному множеству мощности 1.

Итак, поддерживаются два массива целых чисел p и rank. В первом из них для каждого элемента хранятся номер вершины, в которую из него ведет дуга (или номер самой вершины, если это корень дерева). Во втором массиве для корней деревьев хранится величина, называемая рангом и определяемая следующим способом: изначально ранг каждого множества полагается равным 0. В дальнейшем ранг корня объединения множеств с корнями i и j вычисляется как

max(rank[i], rank[j], min(rank[i], rank[j]) + 1)

При этом значения для вершин, не являющихся корнями своих деревьев, не изменяются. Этот массив используется в так называемой эвристике ранга, согласно которой нужно присоединять множества с меньшим рангом к множествам с большим рангом (при этом под рангом множества понимается ранг его корня).

Но основной эффект экономии времени достигается за счет эвристики сжатия путей. Она заключается в том, что каждый раз при поиске корня дерева, вызванном от некоторой вершины, дуги из всех вершин на пути вверх заменяются дугами, ведущими непосредственно к корню, как изображено на рисунке.

Сжатие путей

Процедуры получения представителя и объединения множеств выглядят следующим образом:

Реализация описанных функций

Find-Set(x)
1   if x ≠ p[x]
2       then p[x] ← Find-Set(p[x])
3   return p[x]
Join-Sets(x, y)
1   if rank[x] > rank[y]
2      then p[y] ← x
3           rank[x] ← max(rank[x], rank[y] + 1)
4      else p[x] ← y
5           rank[y] ← max(rank[y], rank[x] + 1)

Оценка времени работы

Приступим к оценке времени работы. Время, затрачиваемое на операцию объединения двух множеств, является константным. Остается подсчитать амортизированную стоимость нахождения представителя. Для этого нам понадобятся несколько предварительных оценок. Пусть множество содержит n элементов, и выполняется последовательность из m операций нахождения корня дерева. Отметим сначала, что для каждой вершины, не являющейся корнем, значение ранга корня ее дерева больше ранга этой вершины и является неубывающей функцией. При этом после присоединения вершины ранга k к какой-то другой ранг объединения будет строго больше k. Следовательно, если сохраняется значение ранга корня некоторого дерева, то и сам этот корень не изменяется. По индукции легко доказать, что количество вершин в поддереве вершины с рангом k хотя бы 2k. Действительно, для вершин с рангом 0 это утверждение верно. Вершина ранга k появляется при объединении двух вершин ранга k − 1, в поддеревьях каждой из которых по предположению 2k−1 вершин. Учитывая, что

2k = 2k−1 + 2k−1

устанавливаем и правомерность индукционного перехода. Покажем теперь, что для любого k количество вершин ранга k не превосходит n / (2k). Когда вершина u только получает ранг k, размер ее поддерева

|S(uk)| ≥ 2k

Никакая вершина не может лежать в множествах S(u, k) и S(v, k) для разных u и v, поскольку, если вершина ранга k перестает быть корнем некоторого дерева, то ранг множества, получающегося после объединения, уже хотя бы k + 1. Очевидно, что из множества вершин можно выделить не более n/(2k) дизъюнктных множеств размера 2k, откуда получаем требуемое. В частности, из этого следует, что ранг любой вершины не превосходит log2n.

Итак, при поиске представителя каждый раз проходится путь вверх от некоторой вершины до корня соответствующего дерева. Назовем теперь дугу u → v идущей «круто вверх», если

rank[v] ≥ 1.5rank[u]

Разделим дуги в каждом пути на три группы:

  1. последние (верхние) дуги в своих путях;
  2. дуги, идущие «круто вверх»
  3. все остальные дуги.

Дуг первой группы в сумме O(m). Ранг любой вершины не превосходит log m, значит дуг второго типа не более log* m. Для каждой вершины ранга k после 1.5k проходов через нее поисков путей, в которых она не является последней или предпоследней, из этой вершины все дуги будут идти «круто вверх».

Действительно, после одного такого прохода вершина становится непосредственно связанной с корнем ее дерева, и, чтобы эта дуга перестала быть последней в пути, необходимо изменение ранга множества, содержащего данную вершину. После 1.5k таких увеличений ранга дуга из рассматриваемой вершины будет всегда идти круто вверх. Выше упоминалось, количество вершин ранга k не превосходит n/2k. Следовательно, общее количество проходов поисков по дугам, третьего типа, равно

k=1…log2n (1,5k)/(2k) ≤ ∑k=1…∞ (3/4)k

что равняется c·n, где c — константа, не зависящая от n и m. Учитывая все вышесказанное, общее время на m операций получения представителя составляет

O(m) + O(m·log* n) + c·n = O(m·log* n)

то есть, амортизировано log*n на одну операцию.

Фибоначчиевы кучи

Фибоначчиевы кучи интересны тем, что их применение позволяет достичь теоретического предела в асимптотике работы некоторых алгоритмов (например, алгоритма Дейкстры). К сожалению, в отличие от системы непересекающихся множеств, здесь константы, скрытые в асимптотической записи, оказываются столь большими, что на практике эта структура данных не находит применения.

Итак, пусть необходимо хранить данные с некоторыми ключами (эти ключи могут принадлежать произвольному множеству с линейным порядком) и осуществлять следующие операции:

  1. добавление элемента;
  2. поиск минимального элемента;
  3. уменьшение ключа некоторого элемента;
  4. изъятие минимального элемента;
  5. удаление произвольного элемента.

Для последних двух операции будет обеспечено амортизированное время выполнения O(logn), для остальных — O(1).

Биномиальное дерево и биномиальная куча

Перед тем, как описывать фибоначчиевы кучи, необходимо рассмотреть более простые структуры — биномиальное дерево и биномиальную кучу. Структура биномиального дерева определяется рекуррентно. Биномиальное дерево B0 порядка 0 состоит из одной вершины. Дерево Bk + 1 получается, если заменить самого левого сына дерева Bk на еще один экземпляр дерева Bk. Несложно показать, что дерево Bk имеет высоту k и содержит 2k вершин.

Биномиальная куча — набор H биномиальных деревьев различных порядков, организованный в виде списка, таких, чтобы в сумме они содержали столько элементов, сколько требуется на данный момент. При этом каждое из деревьев должно обладать свойством кучи (ключ родителя не больше каждого из ключей ее детей). Эта структура данных может использоваться без дальнейшей модификации, но по сравнению с обычными двоичными кучами это дает выигрыш только во времени, затрачиваемом на объединение двух куч.

Фибоначчиева куча и операции с ней

В фибоначчиевой куче корни деревьев, как и дети каждой вершины, объединены в двусторонний циклический список, называемый корневым списком. Для таких списков добавление и удаление элемента, а также слияние двух списков, выполняются за константное время. При этом порядок на детях для нас будет не существенен. Кроме того, структура деревьев теперь становится другой (такая модификация биномиальных деревьев называется фибоначчиевыми деревьями): теперь мы, с определенными ограничениями, разрешаем удалять из них некоторые вершины. Для каждой вершины будем хранить пометку, удалялись ли у нее дети. При этом, если вершина не принадлежит корневому списку и уже обладает пометкой, то ее поддерево расформировывается, а элементы переносятся в корневой список. По индукции можно показать, что фибоначчиево дерево, в котором наибольшая степень вершины равна k, содержит не менее Fk вершин (Здесь через Fk обозначено k-е число Фибоначчи). Тогда, поскольку числа Фибоначчи возрастают экспоненциально, ясно, что степень любой вершины равна O(logn). Здесь под n понимается число вершин в куче на данный момент.

Расскажем, как выполняются анонсированные выше операции, одновременно оценивая их амортизированное время выполнения. При этом каждой вершине будет присвоен неотрицательный баланс: если учетная стоимость некоторой операции больше реальной, увеличим его за счет излишка, иначе «расплатимся» единицами времени из баланса (такой метод оценки — другое описание метода потенциалов, мы как бы приводим явное распределение потенциала по элементам структуры). Будем следить за тем, чтобы баланс всех вершин корневого списка равнялся 1, а у тех вершин, которые обладают пометкой, баланс был равен 2. Остальные вершины будут обладать нулевым балансом. При необходимости добавить вершину создается новое дерево из одного элемента. Учетная стоимость операции равняется 2, при этом лишний квант времени уходит на создание баланса. Будем также хранить указатель на минимальный элемент. Если нужно, он обновляется при добавлении элемента. Тогда операция получения минимального элемента будет требовать O(1) времени.

Научимся корректно извлекать из кучи минимальный элемент. Сначала удалим минимальный элемент, поместив всех его детей в корневой список. Теперь необходимо просмотреть этот список, чтобы найти, какой элемент будет минимальным теперь.

Выделим массив, в котором будем хранить указатели на корни деревьев, которые уже были просмотрены. Если в некоторый момент в нашем распоряжении оказываются два дерева одинаковых рангов, объединяем их в дерево ранга на единицу больше (на это расходуется время, запасенное в балансе вершин). Таким образом, стоимость всей операции (нужно оплатить еще создание баланса при переносе в корневой список для детей удаленной вершины и операции над массивом рангов) равняется O(logn). Действительно, выше было указано, что количество детей одной вершины составляет O(logn).

Опишем, как происходит уменьшение ключа вершины. Положим учетную стоимость такой операции равной 4. Если при уменьшении ключа не нарушается свойство кучи, никаких дальнейших действий не требуется. В противном случае нужно удалить элемент, а потом добавить заново с меньшим значением ключа в корневой список. Если у родителя удаляемой вершины присутствуют все дети, оставшиеся 2 единицы времени уходят на пополнение ее баланса. Иначе к ним прибавляется ее баланс, и имеющиеся 4 единицы расходуются на удаление уже новой вершины. Этот процесс носит название каскадного вырезания.

С помощью комбинирования двух последних операций можно удалять из кучи произвольный элемент. Достаточно уменьшить ключ этого элемента до значения, меньшего минимума в куче, а затем извлечь минимальный элемент.

Общие замечания

Приведем напоследок несколько замечаний. Начнем с того, что амортизационные оценки могут быть не всегда удовлетворительными. Например, при использовании splay-деревьев (их подробное описание можно найти в статье [3]), во время непосредственной обработки каких-либо запросов могут возникать задержки, которые трудно предсказать. С другой стороны, во многих алгоритмах (например, при поиске максимального потока) для получения окончательного результата требуется провести целую серию операций со структурами данных, и тогда этой проблемы не возникает.

Кроме того, все же ошибочно полагать, что амортизационный анализ на практике используется только при получении оценок времени работы для различных структур данных. Например, оценка времени работы алгоритма Кнута-Морриса-Пратта получается на самом деле именно этим способом. Похожим образом доказывается и оценка для алгоритма нахождения треугольника максимальной площади с вершинами, принадлежащими заданному множеству точек.

Список литературы

  1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 1999.
  2. Бреслав А., Воробьева Е., Кузнецов А. Амортизационный анализ (2004)
  3. Комалева О. Скошенные деревья (2005)

Визуализаторы

  1. Смирнов Ф. Фибоначчиевы кучи (2002)
  2. Прокушкин И. Алгоритм Кнута-Морриса-Пратта (2000)

Игорь Синёв


Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий