Относительно бинарного счетного амортизированного анализа

Question

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

Здесь автор упоминает, как показано ниже.

Мы используем потенциальную функцию, равнуюколичество 1-бит в текущем счетчике.

Вопрос 1: Что означает приведенное выше утверждение?

И еще один вопрос, который у меня возник, заключается в анализе, он упоминается как

n + (n / 2) + (n / 4) + --- не более 2n.как мы получили результат как максимум 2n?

Спасибо!

Answer 1

В данном примере затраты на приращение - это количество выполненных битов.

Т.е. при увеличении с 3 (0b11) до 4 (0b100) стоимость 3 (все три позиции перевернуты)).

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

Чтобы обойти это, используйте потенциальный метод для последовательности операций приращения, начинающихся с 0. Теперь потенциальным является число битов, равное 1.

• φ (0) = 0
• φ (1) = 1
• φ (2) = 1
• φ (3) = 2
• φ (4) = 1 и т. Д.

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

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

См. Также: http://en.wikipedia.org/wiki/Potential_method

Answer 2

Просто используйте геометрическую прогрессию, где a = 1 и r = 1/2. Сумма геометрической прогрессии

     a(1-r^{n})/(1-r).

    Here it is (1-(1/2)^{n})/(1-(1/2)) = 2*(1- (1/2)^n).
As n goes to infinity, it becomes 2.

Answer 3

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

Это легче понять из PDF с рисункомно все это означает, что мы можем использовать отдельную функцию, которая соответствует наименьшей единице, которая в этом случае является битом, и сделать ее эквивалентной некоторому разумному значению, выходящему из функции, например, 1-битное отражение в pdf эквивалентно $ 1,Потенциальная функция позволяет легко выполнять анализ.Он начинается с 0 и должен быть неотрицательным.