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

Question

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

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

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

Answer 1

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

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

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

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

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

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

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

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