Изменения
Опечатка. Слово "дувумя" исправлено на "двумя".
{{Определение|id=knuth_counter|definition= '''Счетчик Кнута''' (англ. ''Knuth's Counter'') {{- --}} структура данных, представленная избыточной двоичной системой счисления, где в которой добавление единицы к любому разряду числу и вычитание единицы выполняется за <tex>O(1)</tex>.}}
{{Определение|id=knuth_counter|definition= Неотрицательное целое число <tex>N</tex> в ''Избыточная двоичная система 'избыточной двоичной системе счисления'' ' записывается в виде последовательности разрядов <tex>(d_n d_{n- двоичная система счисления1} \dotsc d_2 d_1)</tex>, где кроме <tex>n</tex> обозначает количество разрядов в числе, <tex>d_i</tex> {{---}} <tex>i</tex>–й разряд числа <tex>(1 \leqslant i \leqslant n)</tex>, причем <tex>d_i \in \{0 ,1,2\}</tex> и <tex>\sum\limits_{i=1 допустима }^n d_i \cdot 2 в записи числа^{i-1} = N.== Алгоритм ==</tex>Имеется число, записанное в избыточной двоичной системе счисления, необходимо добавить 1 к какому-либо разряду. Будем поддерживать следующий инвариант: в следующем за любой двойкой разряде всегда стоит 0.}}
== Доказательство Счетчик Кнута ==Покажем, что инвариант не нарушится.
== Амортизационная оценка алгоритма ==Воспользуемся методом предоплаты. Будем считать, что каждый раз когда мы начинаем выполнять алгоритм мы берем 2 монетки. Одна будет тратится на изменение текущего разряда и одна запасаться. Таким образом, если в разряде стоит 1, то для него запасена 1 монетка, если стоит 2, то запасено 2 монетки. Проверим все варианты.Пример ====
== Смотри См. также ==
* [[Амортизационный анализ]]
* [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код|Представление целых чисел]] == Источники информации ==* H. Kaplan и R. E. Tarjan. New heap data structures. 1998* M. J. Clancy и D. E. Knuth. A programming and problem-solving seminar. Technical Report STAN-CS-77-606, Department of Computer Sciencr, Stanford University, Palo Alto, 1977.* G. S. Brodal. Worst case priority queues. ''Proc. 7th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 96)'', страницы 52-58. ACM Press, 1996.* H. Kaplan и R. E. Tarjan. Purely functional representations of catenable sorted lists. ''Proceedings of the 28th Annual ACM Symposium of Computing'', страницы 202-211. ACM Press, 1996* [http://www.cphstl.dk/Paper/Numeral-systems/mfcs-13.pdf In-Place Binary Counter]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]