Амортизированный анализ на счетчике мощности 3

Question

Я читал учебник по алгоритмам Кормена, Лизерсона, Ривеста и Штейна чаще, чем нет.

Одна из интересных глав там - Амортизированный анализ. Двоичный счетчик - сложный пример, когда дело доходит до выбора Потенциальных функций. Мне было интересно, что если счетчик, если степень 3 с некоторыми коэффициентами (например, х1 * 1 + х2 * 3 + х3 * 9 + ...).

Как определить функцию Потенциала в этом случае?

Answer 1

Чтобы доказать, что увеличение счетчика base-3 требует постоянного амортизированного времени, вы можете использовать потенциальный метод с числом 2 в текущем значении в качестве потенциальной функции.

Операция приращения может быть разделена на 2 части:

1. Смежные 2 в конце значения изменяются на 0.

2. Первая цифра слева от этих 2 с увеличивается.

Шаг (1) принимает работу, пропорциональную количеству 2s, удаленных из состояния.

Каждая из этих 2 добавляется на шаге (2) из ​​предыдущей операции, которая занимает постоянное время и добавляет не более одного 2.

Пусть Φ - это число 2 в текущем состоянии.

• Шаг (1) занимает время, пропорциональное величине, на которую он уменьшается Φ. Поскольку Φ всегда> = 0, общая работа, выполненная на шаге (1) с большим количеством приращений, максимально пропорциональна общей сумме, на которую была увеличена Φ.
• В каждом приращении шаг (2) занимает постоянное время и увеличивает Φ - общую работу, которая может закончиться выполнением шага (1) --- не более чем на 1, представляя постоянный объем фактически выполненной работы, и постоянный объем работы в очереди на шаг (1). Вместе это постоянный объем работы, амортизируемый по текущему и будущему приращениям.