Рубрики

Анализ алгоритма | Набор 5 (Амортизированный анализ Введение)

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

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

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

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

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

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

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

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

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

Источники:
Беркли лекция 35: амортизированный анализ
Лекция MIT 13: Амортизированные алгоритмы, удвоение таблицы, потенциальный метод

http://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec20-amortized/amortized.htm

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

Рекомендуемые посты:

Анализ алгоритма | Набор 5 (Амортизированный анализ Введение)

0.00 (0%) 0 votes