Введение в амортизированный анализ

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

Рассмотрим пример простой вставки в хеш-таблицу. Как определить размер стола? Существует компромисс между пространством и временем: если мы делаем размер хеш-таблицы большим, время поиска становится меньше, но требуемое пространство становится большим.

Решением этой проблемы компромисса является использование динамической таблицы (или массивов). Идея состоит в том, чтобы увеличивать размер таблицы всякий раз, когда она заполняется. Ниже приведены шаги, которые необходимо выполнить, когда таблица заполнится.
1) Выделите память для большего размера таблицы, обычно в два раза больше старой таблицы.
2) Скопируйте содержимое старой таблицы в новую таблицу.
3) Освободите старую таблицу.

Если в таблице есть свободное место, мы просто вставляем новый элемент в доступное место.

Какова временная сложность n вставок по приведенной выше схеме?
Если мы используем простой анализ, стоимость вставки в наихудшем случае составляет O (n). Следовательно, стоимость n вставок в наихудшем случае равна n * O(n), что равно O(n ² ). Этот анализ дает верхнюю границу, но не точную верхнюю границу для n вставок, поскольку все вставки не занимают Θ(n) времени.

Таким образом, используя амортизированный анализ, мы можем доказать, что схема динамической таблицы имеет время вставки O(1), что является отличным результатом для хеширования. Кроме того, концепция динамической таблицы используется в векторах в C++ и ArrayList в Java.

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

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

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

Амортизированный анализ вставки в Red-Black Tree

Давайте обсудим амортизированный анализ операций красно-черного дерева (вставка) с использованием потенциального метода.

Для выполнения амортизированного анализа операции «Вставка красно-черного дерева» мы используем метод «Потенциал» (или «Физик»). Для потенциального метода определим потенциальную функцию который отображает структуру данных в неотрицательное действительное значение. Операция может привести к изменению этого потенциала.

Определим потенциальную функцию следующим образом:

(1)

где n — узел красно-черного дерева

Возможная функция знак равно , по всем узлам красно-черного дерева.

Далее определим амортизированное время операции как:

Амортизированное время = c + (час)

(ч) = (ч') - (час)
где h и h' — состояния красно-черного дерева до и после операции соответственно.
c - фактическая стоимость операции

Изменение потенциала должно быть положительным для низкозатратных операций и отрицательным для высокозатратных операций.

Новый узел вставляется в лист красно-черного дерева. У нас есть листья красно-черного дерева любого из следующих типов:

Вставки и их амортизированный анализ можно представить в виде:
(1)

Эта вставка выполняется путем перекрашивания сначала родителя, а другого родственного элемента (красного). Затем прародитель и дядя этого листового узла рассматриваются для дальнейшего перекрашивания, что приводит к амортизированной стоимости , равной -1 (когда прародитель листового узла красный), -2 (когда дядя листа черный, а прародитель - черный) или +1 (когда дядя листа красный, а прародитель черный). Вставка может быть представлена как:

(2)

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

Таким образом, амортизированная стоимость этой вставки равна 0 .

(3)

В этой вставке мы не можем перекрасить листовой узел, его родителя и брата так, чтобы глубина черного осталась такой же, как и раньше. Итак, нам нужно выполнить поворот влево-влево.

После поворота нет никаких изменений, когда дедушка и бабушка g (вставленный узел) черный. Кроме того, для случая красного прародителя g (вставленный узел) у нас нет никаких изменений. Таким образом, вставка завершена с амортизированной стоимостью = +2 . Вставка была изображена ниже:

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

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

(час) н
где n - общее количество узлов

Таким образом, общая амортизированная стоимость вставки в красно-черное дерево составляет O(n) .

Если у вас возникнут сомнения относительно вставок в красно-черное дерево, вы можете обратиться к разделу Вставки в красно-черное дерево.

Для получения более подробной информации см.:
Проектирование и анализ алгоритмов.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или если вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.