http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=Arthurii&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-29T00:46:47ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%87%D1%91%D1%82%D1%87%D0%B8%D0%BA_%D0%9A%D0%BD%D1%83%D1%82%D0%B0&diff=71740Счётчик Кнута2019-07-10T15:07:41Z<p>Arthurii: 2 поправки орфографии.</p>
<hr />
<div>{{Определение<br />
|id=knuth_counter<br />
|definition= '''Счетчик Кнута''' (англ. ''Knuth's Counter'') {{---}} структура данных, представленная избыточной двоичной системой счисления, в которой добавление единицы к числу и вычитание единицы выполняется за <tex>O(1)</tex>.<br />
}}<br />
<br />
{{Определение<br />
|id=knuth_counter<br />
|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>&ndash;й разряд числа <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.<br />
</tex><br />
}}<br />
<br />
Заметим, что в этой системе представление числа неоднозначно, например представление <tex>212</tex> эквивалентно <tex>1100</tex>.<br />
<br />
== Счетчик Кнута ==<br />
<br />
==== Описание операции инкремента ====<br />
<br />
Оригинальный метод предложен Кнутом и состоит из двух действий:<br />
<br />
# Найти младший разряд <tex>d_i</tex> равный <tex>2</tex> и, если таковой имеется, заменить последовательность <tex>(\dotsc d_{i+1}d_i \dotsc)</tex> на <tex>(\dotsc (d_{i+1}+1)0 \dotsc)</tex><br />
# Заменить <tex>d_1</tex> на <tex>d_1+1</tex>.<br />
<br />
Чтобы достичь необходимой оценки и не выполнять каждый раз поиск для первого правила, можно хранить односвязный [[Список|список]] позиций двоек в числе. Тогда, чтобы найти младший разряд равный двум, нужно просто взять первый элемент списка. Также, непосредственно перед изменением значений разрядов, необходимо выполнять следующие дополнительные действия:<br />
<br />
# Если <tex>d_{i+1}=1</tex>, то заменить первый элемент списка с <tex>i</tex> на <tex>i+1</tex>, иначе удалить его.<br />
# Если <tex>d_1=1</tex>, то добавить в начало списка <tex>1</tex>.<br />
<br />
==== Инвариант с нулем ====<br />
<br />
Проблемой может оказаться появление двух последовательных двоек, при этом первое правило может породить<br />
тройку. То есть недопустима следующая ситуация: <br />
<br />
<tex>(\dotsc 22\dotsc) \overset{Inc} {\longmapsto} (\dotsc 30\dotsc)</tex>.<br />
<br />
В свою очередь такая ситуация получается из этой:<br />
<br />
<tex>(\dotsc 212\dotsc) \overset{Inc} {\longmapsto} (\dotsc 220\dotsc)</tex><br />
<br />
Причем количество единиц между двойками может быть любое, в итоге это приведет к появлению тройки.<br />
Однако если между любой парой двоек всегда будет находиться хотя бы один<br />
<tex>0</tex>, то такой ситуации не возникнет. Покажем, что этот инвариант<br />
поддерживается после инкремента, рассмотрев возможные ситуации:<br />
: Число двоек не изменяется<br />
:: <tex>(\dotsc 2\dotsc 0\dotsc 12\dotsc 0) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 0\dotsc 20\dotsc 1)</tex>.<br />
:: <tex>(\dotsc 02\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 10\dotsc 2)</tex>.<br />
:: <tex>(\dotsc 2\dotsc 02\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 10\dotsc 2)</tex> (частный случай предыдущего).<br />
:: <tex>(\dotsc 12) \overset{Inc} {\longmapsto} (\dotsc 21)</tex>.<br />
: Пропадает одна двойка<br />
:: <tex>(\dotsc 02\dotsc 0) \overset{Inc} {\longmapsto} (\dotsc 10\dotsc 1)</tex>.<br />
:: <tex>(\dotsc 02) \overset{Inc} {\longmapsto} (\dotsc 11)</tex>.<br />
: Появление новой двойки<br />
:: <tex>(\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2)</tex> (имеется в виду появление единственной двойки).<br />
:: <tex>(\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 20\dotsc 2)</tex>.<br />
:: <tex>(\dotsc 2\dotsc 0\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 0\dotsc 20\dotsc 2)</tex> (частный случай предыдущего).<br />
<br />
Таким образом мы видим, что <tex>0</tex> всегда сохраняется.<br />
<br />
==== Пример ====<br />
<br />
В таблице можно увидеть как будет изменятья представление при применении данных правил десять раз к нулю (представления чисел от <tex>0</tex> до <tex>9</tex>):<br />
<br />
{| class="wikitable"<br />
|-<br />
! Шаг<br />
! Представление<br />
|-<br />
| 0 <br />
| 0<br />
|-<br />
| 1 <br />
| 1<br />
|-<br />
| 2 <br />
| 2<br />
|-<br />
| 3 <br />
| 11<br />
|-<br />
| 4 <br />
| 12<br />
|-<br />
| 5 <br />
| 21<br />
|-<br />
| 6 <br />
| 102<br />
|-<br />
| 7 <br />
| 111<br />
|-<br />
| 8 <br />
| 112<br />
|-<br />
| 9 <br />
| 121<br />
|}<br />
<br />
== Обобщение на системы с произвольным основанием ==<br />
<br />
{{Определение<br />
|id=b_ary_rr<br />
|definition=В общем случае подобное представление называется '''<tex>b</tex>-ричным избыточным представлением''' ('''ИП''', англ. ''b-ary redundant representation''), которое похоже на представление в счетчике Кнута, но основание системы может быть произвольным, то есть <tex>d_i \in \{0,1,\dotsc ,b\}</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot b^i = N</tex>, где <tex>b</tex> {{---}} основание. Оно позволяет прибавить единицу к любому разряду, то есть увеличить число на <tex>b^i</tex> за <tex>O(1)</tex><br />
}}<br />
<br />
{{Определение<br />
|id=regular_rr<br />
|definition= Назовем представление '''регулярным''' (англ. ''regular''), если между дувумя разрядами равными <tex>b</tex> есть хотя бы один разряд отличный от <tex>b-1</tex>.<br />
}}<br />
<br />
{{Определение<br />
|id=fixup<br />
|definition= Операция '''исправления''' (англ. ''fix'') разряда <tex>d_i=b</tex> в регулярном ИП увеличивает <tex>d_{i+1}</tex> на <tex>1</tex> и устанавливает <tex>d_i</tex> в <tex>0</tex>, образуя новое регулярное ИП, представляющее то же число, что и <tex>d</tex>.<br />
}}<br />
<br />
Чтобы добавить <tex>1</tex> к разряду <tex>d_i</tex> регулярного ИП <tex>d</tex>,<br />
нужно выполнить следующие действия:<br />
# Если <tex>d_i=b</tex>, исправить <tex>d_i</tex>.<br />
# Если <tex>d_i=b-1</tex> и самый младший значащий разряд <tex>d_j</tex>, такой, что <tex>j>i</tex> и <tex>d_j \ne b-1</tex>, равен <tex>b</tex> (т.е. <tex>d_j=b</tex>), применить операцию исправления к разряду <tex>d_j</tex>.<br />
# Добавить <tex>1</tex> к <tex>d_i</tex>.<br />
# Если <tex>d_i=b</tex>, исправить <tex>d_i</tex>.<br />
<br />
Для реализации данной схемы мы используем односвязный список разрядов от младших<br />
к старшим. В дополнение каждый разряд <tex>d_i</tex> равный <tex>b-1</tex><br />
будет иметь указатель на самый младший разряд <tex>d_j</tex>, такой,<br />
что <tex>j>i</tex> и <tex>d_j \ne b-1</tex>, если он равен <tex>b</tex>,<br />
иначе этот указатель будет на произвольный разряд <tex>d_j</tex> (<tex>j>i</tex>).<br />
Теперь во время увеличения разряда <tex>d_i</tex> на <tex>1</tex> будем проверять<br />
разряд по указателю вперед (п. 2).<br />
<br />
Такое представление позволяет увеличивать произвольный разряд на единицу за константное<br />
время. Обновление указателя вперед происходит следующим образом: когда <tex>d_{i+}</tex> становится равен <tex>b-1</tex> при исправлении разряда <tex>d_{i-1}</tex>, устанавливаем указатель вперед разряда <tex>d_{i}</tex> на <tex>d_{i+1}</tex>, если <tex>d_{i+1}=b</tex>, либо копируем указатель вперед из <tex>d_{i+1}</tex> в <tex>d_{i}</tex>, если <tex>d_{i+1}=b-1</tex>.<br />
При собственно добавлении единицы к разряду <tex>d_i</tex>, также необходимо обновлять его указатель вперед аналогичным образом,<br />
если этот разряд становится равен <tex>b-1</tex>.<br />
<br />
== См. также ==<br />
* [[Амортизационный анализ]]<br />
* [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код|Представление целых чисел]]<br />
<br />
== Источники информации ==<br />
* H. Kaplan и R. E. Tarjan. New heap data structures. 1998<br />
* 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.<br />
* G. S. Brodal. Worst case priority queues. ''Proc. 7th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 96)'', страницы 52-58. ACM Press, 1996.<br />
* 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<br />
* [http://www.cphstl.dk/Paper/Numeral-systems/mfcs-13.pdf In-Place Binary Counter]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Амортизационный анализ]]</div>Arthuriihttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%87%D1%91%D1%82%D1%87%D0%B8%D0%BA_%D0%9A%D0%BD%D1%83%D1%82%D0%B0&diff=71739Счётчик Кнута2019-07-10T15:05:03Z<p>Arthurii: Поправка грамматики.</p>
<hr />
<div>{{Определение<br />
|id=knuth_counter<br />
|definition= '''Счетчик Кнута''' (англ. ''Knuth's Counter'') {{---}} структура данных, представленная избыточной двоичной системой счисления, в которой добавление единицы к числу и вычитание единицы выполняется за <tex>O(1)</tex>.<br />
}}<br />
<br />
{{Определение<br />
|id=knuth_counter<br />
|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>&ndash;й разряд числа <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.<br />
</tex><br />
}}<br />
<br />
Заметим, что в этой системе представление числа неоднозначно, например представление <tex>212</tex> эквивалентно <tex>1100</tex>.<br />
<br />
== Счетчик Кнута ==<br />
<br />
==== Описание операции инкремента ====<br />
<br />
Оригинальный метод предложен Кнутом и состоит из двух действий:<br />
<br />
# Найти младший разряд <tex>d_i</tex> равный <tex>2</tex> и, если таковой имеется, заменить последовательность <tex>(\dotsc d_{i+1}d_i \dotsc)</tex> на <tex>(\dotsc (d_{i+1}+1)0 \dotsc)</tex><br />
# Заменить <tex>d_1</tex> на <tex>d_1+1</tex>.<br />
<br />
Чтобы достичь необходимой оценки и не выполнять каждый раз поиск для первого правила, можно хранить односвязный [[Список|список]] позиций двоек в числе. Тогда, чтобы найти младший разряд равный двум, нужно просто взять первый элемент списка. Также, непосредственно перед изменением значений разрядов, необходимо выполнять следующие дополнительные действия:<br />
<br />
# Если <tex>d_{i+1}=1</tex>, то заменить первый элемент списка с <tex>i</tex> на <tex>i+1</tex>, иначе удалить его.<br />
# Если <tex>d_1=1</tex>, то добавить в начало списка <tex>1</tex>.<br />
<br />
==== Инвариант с нулем ====<br />
<br />
Проблемой может оказаться появление двух последовательных двоек, при этом первое правило может породить<br />
тройку. То есть недопустима следующая ситуация: <br />
<br />
<tex>(\dotsc 22\dotsc) \overset{Inc} {\longmapsto} (\dotsc 30\dotsc)</tex>.<br />
<br />
В свою очередь такая ситуация получается из этой:<br />
<br />
<tex>(\dotsc 212\dotsc) \overset{Inc} {\longmapsto} (\dotsc 220\dotsc)</tex><br />
<br />
Причем количество единиц между двойками может быть любое, в итоге это приведет к появлению тройки.<br />
Однако если между любой парой двоек всегда будет находиться хотя бы один<br />
<tex>0</tex>, то такой ситуации не возникнет. Покажем, что этот инвариант<br />
поддерживается после инкремента, рассмотрев возможные ситуации:<br />
: Число двоек не изменяется<br />
:: <tex>(\dotsc 2\dotsc 0\dotsc 12\dotsc 0) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 0\dotsc 20\dotsc 1)</tex>.<br />
:: <tex>(\dotsc 02\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 10\dotsc 2)</tex>.<br />
:: <tex>(\dotsc 2\dotsc 02\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 10\dotsc 2)</tex> (частный случай предыдущего).<br />
:: <tex>(\dotsc 12) \overset{Inc} {\longmapsto} (\dotsc 21)</tex>.<br />
: Пропадает одна двойка<br />
:: <tex>(\dotsc 02\dotsc 0) \overset{Inc} {\longmapsto} (\dotsc 10\dotsc 1)</tex>.<br />
:: <tex>(\dotsc 02) \overset{Inc} {\longmapsto} (\dotsc 11)</tex>.<br />
: Появление новой двойки<br />
:: <tex>(\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2)</tex> (имеется в виду появление единственной двойки).<br />
:: <tex>(\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 20\dotsc 2)</tex>.<br />
:: <tex>(\dotsc 2\dotsc 0\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 0\dotsc 20\dotsc 2)</tex> (частный случай предыдущего).<br />
<br />
Таким образом мы видим, что <tex>0</tex> всегда сохраняется.<br />
<br />
==== Пример ====<br />
<br />
В таблице можно увидеть как будет изменятья представление при применении данных правил десять раз к нулю (представления чисел от <tex>0</tex> до <tex>9</tex>):<br />
<br />
{| class="wikitable"<br />
|-<br />
! Шаг<br />
! Представление<br />
|-<br />
| 0 <br />
| 0<br />
|-<br />
| 1 <br />
| 1<br />
|-<br />
| 2 <br />
| 2<br />
|-<br />
| 3 <br />
| 11<br />
|-<br />
| 4 <br />
| 12<br />
|-<br />
| 5 <br />
| 21<br />
|-<br />
| 6 <br />
| 102<br />
|-<br />
| 7 <br />
| 111<br />
|-<br />
| 8 <br />
| 112<br />
|-<br />
| 9 <br />
| 121<br />
|}<br />
<br />
== Обобщение на системы с произвольным основанием ==<br />
<br />
{{Определение<br />
|id=b_ary_rr<br />
|definition=В общем случае подобное представление называется '''<tex>b</tex>-ричным избыточным представлением''' ('''ИП''', англ. ''b-ary redundant representation''), которое похоже на представление в счетчике Кнута, но основание системы может быть произвольным, то есть <tex>d_i \in \{0,1,\dotsc ,b\}</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot b^i = N</tex>, где <tex>b</tex> {{---}} основание. Оно позволяет прибавить единицу к любому разряду, то есть увеличить число на <tex>b^i</tex> за <tex>O(1)</tex><br />
}}<br />
<br />
{{Определение<br />
|id=regular_rr<br />
|definition= Назовем представление '''регулярным''' (англ. ''regular''), если между дувумя разрядами равными <tex>b</tex> есть хотя бы один разряд отличный от <tex>b-1</tex>.<br />
}}<br />
<br />
{{Определение<br />
|id=fixup<br />
|definition= Операция '''исправления''' (англ. ''fix'') разряда <tex>d_i=b</tex> в регулярном ИП увеличивает <tex>d_{i+1}</tex> на <tex>1</tex> и устанавливает <tex>d_i</tex> в <tex>0</tex>, образуая новое регуляроне ИП, представляющее то же число, что и <tex>d</tex>.<br />
}}<br />
<br />
Чтобы добавить <tex>1</tex> к разряду <tex>d_i</tex> регулярного ИП <tex>d</tex>,<br />
нужно выполнить следующие действия:<br />
# Если <tex>d_i=b</tex>, исправить <tex>d_i</tex>.<br />
# Если <tex>d_i=b-1</tex> и самый младший значащий разряд <tex>d_j</tex>, такой, что <tex>j>i</tex> и <tex>d_j \ne b-1</tex>, равен <tex>b</tex> (т.е. <tex>d_j=b</tex>), применить операцию исправления к разряду <tex>d_j</tex>.<br />
# Добавить <tex>1</tex> к <tex>d_i</tex>.<br />
# Если <tex>d_i=b</tex>, исправить <tex>d_i</tex>.<br />
<br />
Для реализации данной схемы мы используем односвязный список разрядов от младших<br />
к старшим. В дополнение каждый разряд <tex>d_i</tex> равный <tex>b-1</tex><br />
будет иметь указатель на самый младший разряд <tex>d_j</tex>, такой,<br />
что <tex>j>i</tex> и <tex>d_j \ne b-1</tex>, если он равен <tex>b</tex>,<br />
иначе этот указатель будет на произвольный разряд <tex>d_j</tex> (<tex>j>i</tex>).<br />
Теперь во время увеличения разряда <tex>d_i</tex> на <tex>1</tex> будем проверять<br />
разряд по указателю вперед (п. 2).<br />
<br />
Такое представление позволяет увеличивать произвольный разряд на единицу за константное<br />
время. Обновление указателя вперед происходит следующим образом: когда <tex>d_{i+}</tex> становится равен <tex>b-1</tex> при исправлении разряда <tex>d_{i-1}</tex>, устанавливаем указатель вперед разряда <tex>d_{i}</tex> на <tex>d_{i+1}</tex>, если <tex>d_{i+1}=b</tex>, либо копируем указатель вперед из <tex>d_{i+1}</tex> в <tex>d_{i}</tex>, если <tex>d_{i+1}=b-1</tex>.<br />
При собственно добавлении единицы к разряду <tex>d_i</tex>, также необходимо обновлять его указатель вперед аналогичным образом,<br />
если этот разряд становится равен <tex>b-1</tex>.<br />
<br />
== См. также ==<br />
* [[Амортизационный анализ]]<br />
* [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код|Представление целых чисел]]<br />
<br />
== Источники информации ==<br />
* H. Kaplan и R. E. Tarjan. New heap data structures. 1998<br />
* 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.<br />
* G. S. Brodal. Worst case priority queues. ''Proc. 7th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 96)'', страницы 52-58. ACM Press, 1996.<br />
* 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<br />
* [http://www.cphstl.dk/Paper/Numeral-systems/mfcs-13.pdf In-Place Binary Counter]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Амортизационный анализ]]</div>Arthuriihttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%87%D1%91%D1%82%D1%87%D0%B8%D0%BA_%D0%9A%D0%BD%D1%83%D1%82%D0%B0&diff=71738Счётчик Кнута2019-07-10T15:02:55Z<p>Arthurii: 3 поправки языка.</p>
<hr />
<div>{{Определение<br />
|id=knuth_counter<br />
|definition= '''Счетчик Кнута''' (англ. ''Knuth's Counter'') {{---}} структура данных, представленная избыточной двоичной системой счисления, в которой добавление единицы к числу и вычитание единицы выполняется за <tex>O(1)</tex>.<br />
}}<br />
<br />
{{Определение<br />
|id=knuth_counter<br />
|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>&ndash;й разряд числа <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.<br />
</tex><br />
}}<br />
<br />
Заметим, что в этой системе представление числа неоднозначно, например представление <tex>212</tex> эквивалентно <tex>1100</tex>.<br />
<br />
== Счетчик Кнута ==<br />
<br />
==== Описание операции инкремента ====<br />
<br />
Оригинальный метод предложен Кнутом и состоит из двух действий:<br />
<br />
# Найти младший разряд <tex>d_i</tex> равный <tex>2</tex> и, если таковой имеется, заменить последовательность <tex>(\dotsc d_{i+1}d_i \dotsc)</tex> на <tex>(\dotsc (d_{i+1}+1)0 \dotsc)</tex><br />
# Заменить <tex>d_1</tex> на <tex>d_1+1</tex>.<br />
<br />
Чтобы достичь необходимой оценки и не выполнять каждый раз поиск для первого правила, можно хранить односвязный [[Список|список]] позиций двоек в числе. Тогда, чтобы найти младший разряд равный двум, нужно просто взять первый элемент списка. Также, непосредственно перед изменением значений разрядов, необходимо выполнять следующие дополнительные действия:<br />
<br />
# Если <tex>d_{i+1}=1</tex>, то заменить первый элемент списка с <tex>i</tex> на <tex>i+1</tex>, иначе удалить его.<br />
# Если <tex>d_1=1</tex>, то добавить в начало списка <tex>1</tex>.<br />
<br />
==== Инвариант с нулем ====<br />
<br />
Проблемой может оказаться появление двух последовательных двоек, при этом первое правило может породить<br />
тройку. То есть недопустима следующая ситуация: <br />
<br />
<tex>(\dotsc 22\dotsc) \overset{Inc} {\longmapsto} (\dotsc 30\dotsc)</tex>.<br />
<br />
В свою очередь такая ситуация получается из этой:<br />
<br />
<tex>(\dotsc 212\dotsc) \overset{Inc} {\longmapsto} (\dotsc 220\dotsc)</tex><br />
<br />
Причем количество единиц между двойками может быть любое, в итоге это приведет к появлению тройки.<br />
Однако если между любой парой двоек всегда будет находиться хотя бы один<br />
<tex>0</tex>, то такой ситуации не возникнет. Покажем, что этот инвариант<br />
поддерживается после инкремента, рассмотрев возможные ситуации:<br />
: Число двоек не изменяется<br />
:: <tex>(\dotsc 2\dotsc 0\dotsc 12\dotsc 0) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 0\dotsc 20\dotsc 1)</tex>.<br />
:: <tex>(\dotsc 02\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 10\dotsc 2)</tex>.<br />
:: <tex>(\dotsc 2\dotsc 02\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 10\dotsc 2)</tex> (частный случай предыдущего).<br />
:: <tex>(\dotsc 12) \overset{Inc} {\longmapsto} (\dotsc 21)</tex>.<br />
: Пропадает одна двойка<br />
:: <tex>(\dotsc 02\dotsc 0) \overset{Inc} {\longmapsto} (\dotsc 10\dotsc 1)</tex>.<br />
:: <tex>(\dotsc 02) \overset{Inc} {\longmapsto} (\dotsc 11)</tex>.<br />
: Появление новой двойки<br />
:: <tex>(\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2)</tex> (имеется в виду появление единственной двойки).<br />
:: <tex>(\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 20\dotsc 2)</tex>.<br />
:: <tex>(\dotsc 2\dotsc 0\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 0\dotsc 20\dotsc 2)</tex> (частный случай предыдущего).<br />
<br />
Таким образом мы видим, что <tex>0</tex> всегда сохраняется.<br />
<br />
==== Пример ====<br />
<br />
В таблице можно увидеть как будет изменятья представление при применении данных правил десять раз к нулю (представления чисел от <tex>0</tex> до <tex>9</tex>):<br />
<br />
{| class="wikitable"<br />
|-<br />
! Шаг<br />
! Представление<br />
|-<br />
| 0 <br />
| 0<br />
|-<br />
| 1 <br />
| 1<br />
|-<br />
| 2 <br />
| 2<br />
|-<br />
| 3 <br />
| 11<br />
|-<br />
| 4 <br />
| 12<br />
|-<br />
| 5 <br />
| 21<br />
|-<br />
| 6 <br />
| 102<br />
|-<br />
| 7 <br />
| 111<br />
|-<br />
| 8 <br />
| 112<br />
|-<br />
| 9 <br />
| 121<br />
|}<br />
<br />
== Обобщение на системы с произвольным основанием ==<br />
<br />
{{Определение<br />
|id=b_ary_rr<br />
|definition=В общем случае подобное представление называется '''<tex>b</tex>-ричными избыточными представлением''' ('''ИП''', англ. ''b-ary redundant representation''), которое похоже на представление в счетчике Кнута, но основание системы может быть произвольным, то есть <tex>d_i \in \{0,1,\dotsc ,b\}</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot b^i = N</tex>, где <tex>b</tex> {{---}} основание. Оно позволяет прибавить единицу к любому разряду, то есть увеличить число на <tex>b^i</tex> за <tex>O(1)</tex><br />
}}<br />
<br />
{{Определение<br />
|id=regular_rr<br />
|definition= Назовем представление '''регулярным''' (англ. ''regular''), если между дувумя разрядами равными <tex>b</tex> есть хотя бы один разряд отличный от <tex>b-1</tex>.<br />
}}<br />
<br />
{{Определение<br />
|id=fixup<br />
|definition= Операция '''исправления''' (англ. ''fix'') разряда <tex>d_i=b</tex> в регулярном ИП увеличивает <tex>d_{i+1}</tex> на <tex>1</tex> и устанавливает <tex>d_i</tex> в <tex>0</tex>, образуая новое регуляроне ИП, представляющее то же число, что и <tex>d</tex>.<br />
}}<br />
<br />
Чтобы добавить <tex>1</tex> к разряду <tex>d_i</tex> регулярного ИП <tex>d</tex>,<br />
нужно выполнить следующие действия:<br />
# Если <tex>d_i=b</tex>, исправить <tex>d_i</tex>.<br />
# Если <tex>d_i=b-1</tex> и самый младший значащий разряд <tex>d_j</tex>, такой, что <tex>j>i</tex> и <tex>d_j \ne b-1</tex>, равен <tex>b</tex> (т.е. <tex>d_j=b</tex>), применить операцию исправления к разряду <tex>d_j</tex>.<br />
# Добавить <tex>1</tex> к <tex>d_i</tex>.<br />
# Если <tex>d_i=b</tex>, исправить <tex>d_i</tex>.<br />
<br />
Для реализации данной схемы мы используем односвязный список разрядов от младших<br />
к старшим. В дополнение каждый разряд <tex>d_i</tex> равный <tex>b-1</tex><br />
будет иметь указатель на самый младший разряд <tex>d_j</tex>, такой,<br />
что <tex>j>i</tex> и <tex>d_j \ne b-1</tex>, если он равен <tex>b</tex>,<br />
иначе этот указатель будет на произвольный разряд <tex>d_j</tex> (<tex>j>i</tex>).<br />
Теперь во время увеличения разряда <tex>d_i</tex> на <tex>1</tex> будем проверять<br />
разряд по указателю вперед (п. 2).<br />
<br />
Такое представление позволяет увеличивать произвольный разряд на единицу за константное<br />
время. Обновление указателя вперед происходит следующим образом: когда <tex>d_{i+}</tex> становится равен <tex>b-1</tex> при исправлении разряда <tex>d_{i-1}</tex>, устанавливаем указатель вперед разряда <tex>d_{i}</tex> на <tex>d_{i+1}</tex>, если <tex>d_{i+1}=b</tex>, либо копируем указатель вперед из <tex>d_{i+1}</tex> в <tex>d_{i}</tex>, если <tex>d_{i+1}=b-1</tex>.<br />
При собственно добавлении единицы к разряду <tex>d_i</tex>, также необходимо обновлять его указатель вперед аналогичным образом,<br />
если этот разряд становится равен <tex>b-1</tex>.<br />
<br />
== См. также ==<br />
* [[Амортизационный анализ]]<br />
* [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код|Представление целых чисел]]<br />
<br />
== Источники информации ==<br />
* H. Kaplan и R. E. Tarjan. New heap data structures. 1998<br />
* 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.<br />
* G. S. Brodal. Worst case priority queues. ''Proc. 7th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 96)'', страницы 52-58. ACM Press, 1996.<br />
* 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<br />
* [http://www.cphstl.dk/Paper/Numeral-systems/mfcs-13.pdf In-Place Binary Counter]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Амортизационный анализ]]</div>Arthuriihttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C&diff=71737Очередь2019-07-10T14:56:35Z<p>Arthurii: Поправка грамматики.</p>
<hr />
<div>== Определение ==<br />
[[Файл: Fifo_new.png|right|150px]]<br />
'''Очередь''' (англ. ''queue'') {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <tex> \mathtt{push} </tex> и <tex> \mathtt{pop} </tex> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. ''first-in, first-out {{---}} FIFO''). У очереди имеется '''голова''' (англ. ''head'') и '''хвост''' (англ. ''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове. Очередь поддерживает следующие операции:<br />
* <tex> \mathtt{empty} </tex> {{---}} проверка очереди на наличие в ней элементов,<br />
* <tex> \mathtt {push} </tex> (запись в очередь) {{---}} операция вставки нового элемента,<br />
* <tex> \mathtt{pop} </tex> (снятие с очереди) {{---}} операция удаления нового элемента,<br />
* <tex> \mathtt{size} </tex> {{---}} операция получения количества элементов в очереди.<br />
<br />
== Реализация циклической очереди на массиве ==<br />
Очередь, способную вместить не более <tex>\mathtt{n}</tex> элементов, можно реализовать с помощью массива <tex>\mathtt{elements[0\dots n-1]}</tex>. Она будет обладать следующими полями:<br />
* <tex>\mathtt{head}</tex> {{---}} голова очереди,<br />
* <tex>\mathtt{tail}</tex> {{---}} хвост очереди.<br />
<br />
=== empty ===<br />
'''boolean''' empty():<br />
'''return''' head == tail<br />
<br />
=== push ===<br />
'''function''' push(x : '''T'''):<br />
'''if''' (size() != n)<br />
elements[tail] = x<br />
tail = (tail + 1) % n<br />
<br />
=== pop ===<br />
'''T''' pop():<br />
'''if''' (empty()) <br />
'''return null'''<br />
x = elements[head]<br />
head = (head + 1) % n<br />
'''return''' x<br />
<br />
=== size ===<br />
'''int''' size()<br />
'''if''' head > tail<br />
'''return''' n - head + tail<br />
'''else'''<br />
'''return''' tail - head<br />
Из-за того что нам не нужно снова выделять память, каждая операция выполняется за <tex>O(1)</tex> времени.<br />
<br />
'''Плюсы:'''<br />
* проста в разработке,<br />
* по сравнению с реализацией на списке есть незначительная экономия памяти.<br />
'''Минусы:'''<br />
* количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива),<br />
* при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив.<br />
<br />
== Реализация на списке ==<br />
Для данной реализации очереди необходимо создать [[Список | список]] <tex>list</tex> и операции работы на созданном списке.<br />
<br />
Реализация очереди на односвязном списке:<br />
=== List ===<br />
* <code>ListItem(data : '''T''', next : '''ListItem''')</code> {{---}} конструктор,<br />
* <tex>\mathtt{x.value}</tex> {{---}} поле, в котором хранится значение элемента,<br />
* <tex>\mathtt{x.next}</tex> {{---}} указатель на следующий элемент очереди.<br />
<br />
=== push ===<br />
'''function''' push(x : '''T'''):<br />
element = tail<br />
tail = ListItem(x, NULL)<br />
'''if''' size == 0<br />
head = tail<br />
'''else''' <br />
element.next = tail<br />
size++<br />
<br />
=== pop ===<br />
'''T''' pop(): <br />
size--<br />
element = head<br />
head = head.next<br />
'''return''' element<br />
<br />
=== empty ===<br />
'''boolean''' empty():<br />
'''return''' head == tail<br />
[[Файл: Queue.png|right|230px]]<br />
<br />
'''Плюсы:'''<br />
* каждая операция выполняется за время <tex>O(1)</tex>.<br />
'''Минусы:'''<br />
* память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве.<br />
<br />
== Реализация на двух стеках ==<br />
Очередь можно реализовать на двух [[Стек|стеках]] <tex>\mathtt{leftStack}</tex> и <tex>\mathtt{rightStack}</tex>. Поступим следующим образом: <tex>\mathtt{leftStack}</tex> будем использовать для операции <tex> \mathtt {push} </tex>, <tex>\mathtt{rightStack}</tex> для операции <tex> \mathtt{pop} </tex>. При этом, если при попытке извлечения элемента из <tex>\mathtt{rightStack}</tex> он оказался пустым, просто перенесем все элементы из <tex>\mathtt{leftStack}</tex> в него (при этом элементы в <tex>\mathtt{rightStack}</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>\mathtt{leftStack}</tex> станет пустым).<br />
<br />
* <tex> \mathtt{pushLeft} </tex> и <tex> \mathtt{pushRight} </tex> {{---}} функции, реализующие операцию <tex> \mathtt{push} </tex> для соответствующего стека,<br />
* <tex> \mathtt{popLeft} </tex> и <tex> \mathtt{popRight} </tex> {{---}} аналогично операции <tex> \mathtt {pop} </tex>.<br />
<br />
=== push ===<br />
'''function''' push(x : '''T'''):<br />
pushLeft(x)<br />
=== pop ===<br />
'''T''' pop():<br />
'''if''' '''not''' rightStack.empty()<br />
'''return''' popRight() <br />
'''else'''<br />
'''while''' '''not''' leftStack.empty()<br />
pushRight(popLeft())<br />
'''return''' popRight()<br />
<br />
При выполнении операции <tex> \mathtt{push} </tex> будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию <tex> \mathtt{pop} </tex> из первого стека, третью во второй стек на финальный <tex> \mathtt{pop} </tex>. Тогда для операций <tex> \mathtt{pop} </tex> учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции <tex> \mathtt{push} </tex>.<br />
<br />
Таким образом, для каждой операции требуется <tex>O(1)</tex> монет, а значит, амортизационная стоимость операций <tex>O(1)</tex>.<br />
<br />
'''Плюсы:'''<br />
* эту реализацию несложно модифицировать для получения минимума в текущей очереди за <tex>O(1)</tex>.<br />
'''Минусы:'''<br />
* если <tex>\mathtt{leftStack}</tex> не пуст, то операция <tex> \mathtt{pop} </tex> может выполняться <tex>O(n)</tex> времени, в отличие от других реализаций, где <tex> \mathtt{pop} </tex> всегда выполняется за <tex>O(1)</tex>.<br />
<br />
== Реализация на шести стеках ==<br />
<br />
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим <tex>O(n)</tex> времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с <tex>O(1)</tex> истинного времени на операцию.<br />
<br />
Подробное описание в статье [[Персистентная очередь#Реализация очереди на шести стеках|Персистентная очередь]].<br />
<br />
=== Отличия от других реализаций ===<br />
<br />
'''Плюсы:'''<br />
* <tex>O(1)</tex> реального времени на операцию,<br />
* возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], если использовать [[Персистентный стек|персистентные стеки]]. <br />
<br />
'''Минусы:'''<br />
* дольше в среднем выполняются операции,<br />
* больше расход памяти,<br />
* большая сложность реализации.<br />
<br />
== См. также ==<br />
* [[Стек]]<br />
* [[Персистентная очередь]]<br />
<br />
== Источники информации ==<br />
* [[wikipedia:ru:Очередь_(программирование)|Википедия {{---}} Очередь (программирование)]]<br />
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262<br />
* T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1, p. 262<br />
* [http://hdl.handle.net/1813/6273 ''Hood R., Melville R.'' Real Time Queue Operations in Pure LISP. {{---}} Cornell University, 1980]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Амортизационный анализ]]</div>Arthuriihttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D1%82%D0%B5%D0%BA&diff=71736Стек2019-07-10T14:53:08Z<p>Arthurii: Поправка пунктуации.</p>
<hr />
<div>== Определение ==<br />
[[Файл: lifo.png|thumb|right|200px|Стек]]<br />
'''Стек''' (от англ. ''stack'' {{---}} стопка) {{---}} структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел {{---}} первым вышел» (last-in, first-out {{---}} LIFO). Примером стека в реальной жизни может являться стопка тарелок: когда мы хотим вытащить тарелку, мы должны снять все тарелки выше. Вернемся к описанию операций стека:<br />
* <tex> \mathtt{empty} </tex> {{---}} проверка стека на наличие в нем элементов,<br />
* <tex> \mathtt{push} </tex> (запись в стек) {{---}} операция вставки нового элемента,<br />
* <tex> \mathtt{pop} </tex> (снятие со стека) {{---}} операция удаления нового элемента.<br />
<br />
==Реализации==<br />
Для стека с <tex>n</tex> элементами требуется <tex>O(n)</tex> памяти, так как она нужна лишь для хранения самих элементов.<br />
===На массиве===<br />
Перед реализацией стека выделим ключевые поля:<br />
* <tex>\mathtt{s[1\dots n]} </tex> {{---}} массив, с помощью которого реализуется стек, способный вместить не более <tex>n</tex> элементов,<br />
* <tex>\mathtt{s.top}</tex> {{---}} индекс последнего помещенного в стек элемента.<br />
<br />
Стек состоит из элементов <tex>\mathtt {s[1\dots s.top]}</tex>, где <tex>\mathtt{s[1]}</tex> {{---}} элемент на дне стека, а <tex>\mathtt{s[s.top]}</tex> {{---}} элемент на его вершине.<br />
Если <tex>\mathtt{s.top = 0}</tex>, то стек не содержит ни одного элемента и является пустым (англ. ''empty''). Протестировать стек на наличие в нем элементов можно с помощью операции {{---}} запроса <tex> \mathtt{stackEmpty} </tex>. Если элемент снимается с пустого стека, говорят, что он опустошается (англ. ''underflow''), что обычно приводит к ошибке. Если значение <tex>\mathtt{s.top}</tex> больше <tex>\mathtt{n}</tex>, то стек переполняется (англ. ''overflow''). (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.) <br />
<br />
Каждую операцию над стеком можно легко реализовать несколькими строками кода:<br />
<br />
'''boolean''' empty():<br />
'''return''' s.top == 0<br />
<br />
'''function''' push(element : '''T'''):<br />
s.top = s.top + 1<br />
s[s.top] = element<br />
<br />
'''T''' pop():<br />
'''if''' empty()<br />
'''return''' error "underflow"<br />
'''else''' <br />
s.top = s.top - 1<br />
'''return''' s[s.top + 1]<br />
<br />
Как видно из псевдокода выше, все операции со стеком выполняются за <tex>O(1)</tex>.<br />
<br />
===На саморасширяющемся массиве===<br />
Возможна реализация стека на [[Саморасширяющийся_массив| динамическом массиве]], в результате чего появляется существенное преимущество над обычной реализацией: при операции push мы никогда не сможем выйти за границы массива, тем самым избежим ошибки исполнения.<br />
<br />
Создадим вектор и определим операции стека на нём. В функции <tex> \mathtt {push} </tex> Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в <tex> \mathtt {pop} </tex>, перед тем, как изъять элемент из массива, {{---}} не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.<br />
<br />
Ключевые поля:<br />
* <tex>\mathtt{s[0\dots n-1]}</tex> {{---}} старый массив, в котором хранится стек,<br />
* <tex>\mathtt{newStack[0\dots newSize]}</tex> {{---}} временный массив, где хранятся элементы после перекопирования,<br />
* <tex>\mathtt{head}</tex> {{---}} верхушка стека,<br />
* <tex>\mathtt{capacity}</tex> {{---}} размер массива.<br />
<br />
'''function''' push(element : '''T'''):<br />
'''if''' head == capacity - 1<br />
'''T''' newStack[capacity * 2]<br />
'''for''' i = 0 '''to''' capacity - 1<br />
newStack[i] = s[i]<br />
s = newStack<br />
capacity = capacity * 2<br />
head++<br />
s[head] = element<br />
<br />
'''T''' pop():<br />
temp = s[head]<br />
head--<br />
'''if''' head < capacity / 4<br />
'''T''' newStack[capacity / 2]<br />
'''for''' i = 0 '''to''' capacity / 4 - 1<br />
newStack[i] = s[i]<br />
s = newStack<br />
capacity = capacity / 2<br />
'''return''' temp<br />
<br />
===На списке===<br />
Стек можно реализовать и на [[Список | списке]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции <tex> \mathtt{push} </tex> будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью <tex> \mathtt{pop} </tex> будет текущая голова. После вызова функции <tex> \mathtt{push} </tex> текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции <tex> \mathtt{pop} </tex> будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.<br />
<br />
Заведем конструктор вида <code>ListItem(next : '''ListItem''', data : '''T''')</code><br />
<br />
Ключевые поля:<br />
* <tex>\mathtt{head.data}</tex> {{---}} значение в верхушке стека,<br />
* <tex>\mathtt{head.next}</tex> {{---}} значение следующее за верхушкой стека.<br />
<br />
'''function''' push(element : '''T'''):<br />
head = ListItem(head, element)<br />
<br />
'''T''' pop():<br />
data = head.data<br />
head = head.next<br />
'''return''' data<br />
<br />
В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же <tex>\mathtt{n}</tex>. Стоит заметить, что стек требует <tex>O(n)</tex> дополнительной памяти на указатели в списке.<br />
<br />
== См. также ==<br />
* [[Очередь]]<br />
* [[Персистентный стек]]<br />
<br />
== Источники информации ==<br />
* [[wikipedia:ru:Стек|Википедия {{---}} Стек]]<br />
*Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10<br />
*T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1<br />
* [http://comp-science.narod.ru/Progr/Stack.htm Динамические структуры данных: стеки]<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Амортизационный анализ]]<br />
[[Категория:Структуры данных]]</div>Arthuriihttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA&diff=71735Список2019-07-10T14:48:45Z<p>Arthurii: Поправка пунктуации.</p>
<hr />
<div>'''Связный список''' (англ. ''List'') {{---}} структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как [[стек]] и [[очередь]]. <br />
<br />
__TOC__<br />
==Односвязный список ==<br />
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.<br />
[[Файл:simpleSpisok.png|center|400px]]<br />
==Двусвязный список ==<br />
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.<br />
[[Файл:twiceSpisok.png|center|400px]]<br />
===XOR-связный список ===<br />
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.<br />
==Циклический список==<br />
Первый элемент является следующим для последнего элемента списка.<br />
[[Файл:circleSpisok.png|center|450px]]<br />
==Операции на списке==<br />
Рассмотрим базовые операции на примере односвязного списка.<br />
===Вставка===<br />
Очевиден случай, когда необходимо добавить элемент (<tex>newHead</tex>) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.<br />
<br />
'''function''' insert(Node thatElement):<br />
thatElement.next = thisElement.next <br />
thisElement.next = thatElement<br />
[[Файл:insertAfter.png|center|490px]]<br />
<br />
===Поиск===<br />
Для того, чтобы найти элемент по значению (<tex>value</tex>), будем двигаться по списку от головы до конца и сравнивать значение в элементах с искомым. Если элемента в списке нет, то возвращаем <tex>NULL</tex>. <br />
Node search('''int''' value):<br />
node = head<br />
'''while''' node != ''NULL'' '''and''' value != node.value<br />
node = node.next<br />
'''return''' node<br />
<br />
===Удаление===<br />
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.<br />
'''function''' removeHead():<br />
'''if''' head != ''NULL''<br />
tmp = head<br />
head = head.next<br />
'''delete''' tmp<br />
[[Файл:removeHead.png|center|430px]]<br />
Удаление элемента после заданного (<tex>thisElement</tex>) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.<br />
'''function''' removeAfter(Node thisElement):<br />
'''if''' thisElement.next != ''NULL''<br />
tmp = thisElement.next<br />
thisElement.next = thisElement.next.next<br />
'''delete''' tmp<br />
[[Файл:removeAfter.png|center|550px]]<br />
<br />
==Поиск цикла в списке==<br />
Для начала необходимо уметь определять {{---}} список циклический или нет. Воспользуемся алгоритмом Флойда "Черепаха и заяц". Пусть за одну итерацию первый указатель (черепаха) переходит к следующему элементу списка, а второй указатель (заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.<br />
'''boolean''' hasCycle(Node head):<br />
tortoise = head<br />
hare = head<br />
'''repeat'''<br />
'''if''' hare == ''NULL'' '''or''' hare.next == ''NULL'' <br />
'''return''' ''false''<br />
tortoise = tortoise.next<br />
hare = hare.next.next<br />
'''until''' tortoise == hare<br />
'''return''' ''true''<br />
Если цикла не существует, то заяц первым дойдет до конца и функция возвратит <tex>false</tex>. В другом случае, в тот момент, когда и черепаха и заяц находятся в цикле, расстояние между ними будет сокращаться на <tex>1</tex>, что гарантирует их встречу за конечное время.<br />
<br />
==Поиск длины хвоста в списке с циклом==<br />
Так как для поиска хвоста мы должны знать, что цикл существует, воспользуемся предыдущей функцией и при выходе из неё запомним "момент встречи" зайца и черепахи. Назовем её <tex>pointMeeting</tex>.<br />
===Наивные реализации===<br />
====Реализация за <tex>O(n^2)</tex>====<br />
Будем последовательно идти от начала цикла и проверять, лежит ли этот элемент на цикле. На каждой итерации запустим от <tex>pointMeeting</tex> вперёд указатель. Если он окажется в текущем элементе, прежде чем посетит <tex>pointMeeting</tex> снова, то точку окончания (начала) хвоста нашли.<br />
<br />
====Реализация за <tex>O(n \log n)</tex>====<br />
Реализацию, приведенную выше можно улучшить. Для этого воспользуемся [[Целочисленный_двоичный_поиск | бинарным поиском]]. Сначала проверим голову списка, потом сделаем <tex> 2 </tex> шага вперёд, потом <tex> 4 </tex>, потом <tex> 8 </tex> и так далее, пока не окажемся на цикле. Теперь у нас есть две позиции {{---}} на левой границе, где мы в хвосте, и на правой {{---}} в цикле. Сделаем бинарный поиск уже по этому отрезку и таким образом найдём цикл за <tex>O(n \log n)</tex>.<br />
<br />
===Эффективная реализация===<br />
Возможны два варианта цикла в списке. Первый вариант {{---}} сам список циклический (указатель <tex>next</tex> последнего элемента равен первому), а второй вариант {{---}} цикл внутри списка (указатель <tex>next</tex> последнего элемента равен любому другому (не первому)). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Достаточно запустить один указатель из <tex>pointMeeting</tex>, а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла. Сложность алгоритма {{---}} <tex>O(n)</tex>.<br />
Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка. <br />
'''int''' getTail(Node head, Node pointMeeting):<br />
firstElement = head.next<br />
secondElement = pointMeeting.next<br />
lengthTail = 1<br />
'''while''' firstElement != secondElement<br />
firstElement = firstElement.next<br />
secondElement = secondElement.next<br />
lengthTail = lenghtTail + 1<br />
'''return''' lengthTail<br />
====Доказательство корректности алгоритма====<br />
Рассмотрим цикл длиной <tex>N</tex> с хвостом длины <tex>L</tex>. Напишем функции для обоих указателей в зависимости от шага <tex>n</tex>. Очевидно, что встреча не может произойти при <tex>n \leqslant L</tex>, так как в этом случае <tex>2n>n</tex> для любого <tex>n>0</tex>. Тогда положения указателей зададутся следующими функциями (при <tex>n>L</tex>):<br />
<br />
<tex>f_1(n) = L + (n-L) \bmod N</tex><br />
<br />
<tex>f_2(n) = L + (2n-L) \bmod N</tex><br />
<br />
Приравнивая, получим <tex>n \bmod N = 0</tex>, или <tex>n = k N, n > L</tex>.<br />
Пусть <tex>H</tex> {{---}} голова списка, <tex>X</tex> {{---}} точка встречи, <tex>A</tex> {{---}} первый элемент цикла, <tex>Q</tex> {{---}} расстояние от <tex>X</tex> до <tex>A</tex>. Тогда в точку <tex>A</tex> можно прийти двумя путями: из <tex>H</tex> в <tex>A</tex> длиной <tex>L</tex> и из <tex>H</tex> через <tex>X</tex> в <tex>A</tex> длиной <tex>L + N = X + Q</tex>, то есть:<br />
<br />
<tex>Q = L + N - X</tex>, но так как <tex>X = kN</tex><br />
<br />
<tex>Q = L + (1-k) N</tex><br />
<br />
Пусть <tex>L = p N + M, 0 \leqslant M < N</tex><br />
<br />
Известно, что<br />
<br />
<tex>L < k N \leqslant L + N</tex><br />
<br />
<tex>pN + M < kN \leqslant (p+1)N + M</tex> откуда <tex>k = p + 1</tex><br />
<br />
Подставив полученные значения, получим:<br />
<tex>Q = pN + M + (1 - p - 1)N = M = L \bmod N</tex>, откуда следует, что если запустить указатели с одной скоростью из <tex>H</tex> и <tex>X</tex>, то они встретятся через <tex>L</tex> шагов в точке <tex>A</tex>. К этому времени вышедший из <tex>H</tex> пройдёт ровно <tex>L</tex> шагов и остановится в <tex>A</tex>, вышедший из <tex>X</tex> накрутит по циклу <tex>[L/N]</tex> шагов и пройдёт ещё <tex>Q = L \bmod N</tex> шагов. Поскольку <tex>L = [L/N] + L \bmod N</tex>, то они встретятся как раз в точке <tex>A</tex>.<br />
<br />
==Задача про обращение списка==<br />
Для того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий.<br />
Эта рекурсивная функция принимает указатель на голову списка и предыдущий элемент (при запуске указывать <tex>NULL</tex>), а возвращает указатель на новую голову списка.<br />
<br />
Node reverse(Node current, Node prev):<br />
'''if''' current == ''NULL''<br />
'''return''' prev<br />
next = current.next<br />
current.next = prev<br />
'''return''' reverse(next, current)<br />
<br />
Алгоритм корректен, поскольку значения элементов в списке не изменяются, а все указатели <tex>next</tex> изменят свое направление, не нарушив связности самого списка. <br />
<br />
==См.также==<br />
* [[Динамический массив]]<br />
<br />
==Источники информации==<br />
* [[wikipedia:Linked_list | Wikipedia {{---}} Linked list]]<br />
* [[wikipedia:ru:Список_(информатика) | Википедия {{---}} Список]]<br />
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ {{---}} 2-е изд. {{---}} М.: «Вильямс», 2007. {{---}} Глава 11.2. {{---}} ISBN 5-8489-0857-4<br />
* Дональд Э. Кнут Искусство программирования. Том 1. Основные алгоритмы {{---}} 2-е изд. {{---}} М.: «Вильямс», 2012. {{---}} Глава 2.2. {{---}} ISBN 0-201-89685-0<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Амортизационный анализ]]<br />
[[Категория: Структуры данных]]</div>Arthuriihttp://neerc.ifmo.ru/wiki/index.php?title=Hashed_Array_Tree&diff=71734Hashed Array Tree2019-07-10T14:41:03Z<p>Arthurii: Поправка орфографии.</p>
<hr />
<div>'''HAT (Hashed Array Tree)''' {{---}} структура данных, объединяющая в себе некоторые возможности массивов, хэш-таблиц и деревьев. Внешне структура похожа на хеш-таблицу с разрешением коллизий методом цепочек, отсюда и название. В действительности HAT {{---}} это эффективный способ реализовать массивы переменной длины, так как он предлагает хорошую производительность порядка <tex>O(N)</tex>, чтобы добавить <tex>N</tex> элементов к пустому массиву, и требует всего лишь <tex>O(\sqrt{N})</tex> дополнительной памяти. <br />
<br />
==Значимость==<br />
Массивы переменной длины {{---}} наиболее естественная и удобная структура данных для многих приложений, так как они обеспечивают постоянное время доступа к их элементам. Однако при их реализации мы можем столкнуться с двумя основными проблемами: чрезмерное копирование элементов и использование памяти. HAT {{---}} реализация массива переменной длины, решающая обе проблемы и предоставляющая ряд преимуществ по сравнению со стандартными реализациями.<br />
<br />
==Описание структуры==<br />
HAT состоит из главного массива указателей <tex>top</tex> и ряда листьев <tex>leaf</tex> (так же одномерные массивы), в которых хранятся элементы.<br />
Возможное число указателей в главном массиве и возможное число элементов в каждом листе равны между собой и являются степенями двойки. HAT заполняется элементами от самого малого листа к самому большому, при этом каждый лист заполняется слева направо.<br />
===Получение элемента по номеру===<br />
Благодаря использованию степеней двойки, мы можем эффективно находить элементы в HAT, используя поразрядные операции. Пусть размер главного массива и каждого листа будет равен <tex>2^{power}</tex>.<br />
'''int''' topIndex('''int''' j):<br />
<font color=green>// Получить номер указателя в основном массиве</font><br />
'''return''' j >> power<br />
'''int''' leafIndex('''int''' j):<br />
<font color=green>// Получить номер листа</font><br />
'''return''' j & ((1 << power) - 1)<br />
'''T''' getHat('''int''' j):<br />
<font color=green>// Вернуть элемент HAT. Нет проверки на выход за пределы массива.</font><br />
'''return''' top[topIndex(j)][leafIndex(j)]<br />
*<br />
Рассмотрим как происходит вычисление адреса на примере. Пусть у нас есть HAT с размером листа равным <tex>4</tex>, тогда для нашего случая <tex>power = 2</tex>. Получим значения функций для элемента под номером <tex>5</tex>: <br />
*<tex>topIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен операции деления (взятию по модулю) <tex>j</tex> на <tex>2^{2}</tex>. То есть получим <tex>1</tex> {{---}} действительно элемент под номером <tex>5</tex> находится в первом листе (нумерация листов с <tex>0</tex>).<br />
*<tex>leafIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен умножению <tex>1</tex> на <tex>2^{2}</tex>. То есть после вычитания <tex>1</tex> получим число формата <tex>011..11</tex>, в нашем случае {{---}} <tex>011</tex>. Формула для <tex>leafIndex</tex> справедлива, так как элементы, которые находятся в разных листьях и различаются на <tex>2^k</tex>, будут иметь одинаковую позицию в этих листах, а младшие <tex>k</tex> бит у них будут общими. Поэтому сделаем операцию побитовое "и" к запрашиваемому индексу и к <tex> 2^k - 1 </tex> и получим нужный индекс в массиве <tex> leaf </tex>.<br />
<tex>5_{10} = 101_2</tex> , следовательно <tex>101</tex> <tex>\&</tex> <tex>011 = 001</tex>, то есть индекс в листе равен <tex>1</tex> (в листах нумерация тоже с <tex>0</tex>).<br />
<br />
[[Файл:fullHAT.png|200px]]<br />
<br />
===Добавление элементов===<br />
*Чаще всего при добавлении элемента в одном из листьев (последнем незаполненном на данный момент) найдется свободное место, что позволит осуществить быструю вставку {{---}} <tex>O(1)</tex>. <br />
*Реже мы столкнемся со случаем, когда необходимо создать новый лист. Достаточно всего лишь добавить указатель в свободную ячейку главного массива, что также позволит произвести вставку элемента за <tex>O(1)</tex>.<br />
*Самый интересный случай {{---}} когда главный массив и все листья заполнены. Cначала вычислим нужный размер (массивы <tex>top</tex> и <tex>leaf</tex> увеличиваются в <tex>2</tex> раза, то есть <tex>power = power \cdot 2 </tex>), затем скопируем элементы в новую структуру HAT, освобождая старые листья и распределяя новые листья(размер листа изменился, а значит количество элементов в листе и количество используемых листьев так же изменится).<br />
Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивов переменной длины, потому что увеличения размеров всех массивов происходит редко (как будет видно ниже). Копировать элементы мы будем только тогда, когда главный массив полон (достигли соответствующей степени двойки, то есть <tex> N = (2 \cdot 2)^k</tex>, где <tex>k</tex> {{---}} натуральное число), тогда общая сумма перекопирования будет равна <tex>1+4+16+64+256+...+N</tex>. Воспользуемся тождеством: <tex>(x^{n+1} -1)=(x-1)(1+x+x^2+x^3+... + x^k)</tex>, тогда для нашего случая: <tex>1 +4+4^2+4^3+...+4^k = (4^{k+1} -1)/(4-1) = (4N-1)/3</tex>, или около <tex>4N/3</tex>. Это означает, что среднее число дополнительных операций копирования {{---}} <tex>O(N)</tex> для последовательного добавления <tex> N </tex> элементов, а не <tex>O(N^2)</tex>. Мы получили <tex>4N/3</tex> против <tex>2N</tex> в обычном динамическом массиве, то есть константа уменьшилась.<br />
<br />
[[Файл:AlgoF2.gif|400px]]<br />
<br />
===Расход памяти===<br />
HAT использует меньше дополнительной памяти, чем в стандартных подходах к расширению массивов, то есть полном перекопировании и перераспределении всего массива.<br />
Затраты дополнительной памяти (уже выделенной, но еще не используемой) в самом плохом случае {{---}} <tex>(top+leaf-1) ~= 2\sqrt{N} = O(\sqrt{N})</tex> (этот случай при пустой HAT {{---}} в <tex>top</tex> один указатель на единственный пустой лист). <br />
<br />
Если в листе будет <tex>power/2</tex> элементов, то ожидаемая трата дополнительной памяти уменьшается до <tex>(top + leaf/2) \approx 1.5\sqrt{N}</tex>. Таким образом HAT использует <tex>\Theta(\sqrt{N})</tex> дополнительной памяти. Это лучше [[Динамический массив |динамического массива]], который использует <tex>O(N)</tex> дополнительной памяти сразу после перекопирования элементов, и лучше [[Список | списка]].<br />
<br />
==Эффективность==<br />
Благодаря тому, что копирования в HAT происходят реже, чем в других реализациях динамических массивов, и в худшем случае требуется <tex>O(\sqrt{N})</tex> памяти, ее можно использовать в любых программах, требующих работу с массивами переменной длинны, где использование других структур данных (например списков) не удобно. На многих алгоритмах HAT работает значительно быстрее стандартных массивов, дополнительно можно ознакомиться с результатами некоторых тестов<ref>[http://pmg.org.ru/ai/tree_hash.htm Результаты тестов]</ref>.<br />
<br />
== Примечания ==<br />
<references/><br />
<br />
==Источники информации==<br />
*[[wikipedia:en:Hashed array tree | Wikipedia {{---}} Hashed array tree ]]<br />
*Cline, M.P. and G.A. Lomow, C++ FAQs, Reading, MA: Addison-Wesley, 1995. <br />
*Cormen, T.H., C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms, Cambridge, MA: MIT Press, 1990.<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Амортизационный анализ]]<br />
[[Категория:Структуры данных]]</div>Arthuriihttp://neerc.ifmo.ru/wiki/index.php?title=Hashed_Array_Tree&diff=71733Hashed Array Tree2019-07-10T14:29:40Z<p>Arthurii: Поправка пунктуации.</p>
<hr />
<div>'''HAT (Hashed Array Tree)''' {{---}} структура данных, объединяющая в себе некоторые возможности массивов, хэш-таблиц и деревьев. Внешне структура похожа на хеш-таблицу с разрешением коллизий методом цепочек, отсюда и название. В действительности HAT {{---}} это эффективный способ реализовать массивы переменной длины, так как он предлагает хорошую производительность порядка <tex>O(N)</tex>, чтобы добавить <tex>N</tex> элементов к пустому массиву, и требует всего лишь <tex>O(\sqrt{N})</tex> дополнительной памяти. <br />
<br />
==Значимость==<br />
Массивы переменной длины {{---}} наиболее естественная и удобная структура данных для многих приложений, так как они обеспечивают постоянное время доступа к их элементам. Однако при их реализации мы можем столкнуться с двумя основными проблемами: чрезмерное копирование элементов и использование памяти. HAT {{---}} реализация массива переменной длины, решающая обе проблемы и предоставляющая ряд преимуществ по сравнению со стандартными реализациями.<br />
<br />
==Описание структуры==<br />
HAT состоит из главного массива указателей <tex>top</tex> и ряда листьев <tex>leaf</tex> (так же одномерные массивы), в которых хранятся элементы.<br />
Возможное число указателей в главном массиве и возможное число элементов в каждом листе равны между собой и являются степенями двойки. HAT заполняется элементами от самого малого листа к самому большому, при этом каждый лист заполняется слева направо.<br />
===Получение элемента по номеру===<br />
Благодаря использованию степеней двойки, мы можем эффективно находить элементы в HAT, используя поразрядные операции. Пусть размер главного массива и каждого листа будет равен <tex>2^{power}</tex>.<br />
'''int''' topIndex('''int''' j):<br />
<font color=green>// Получить номер указателя в основном массиве</font><br />
'''return''' j >> power<br />
'''int''' leafIndex('''int''' j):<br />
<font color=green>// Получить номер листа</font><br />
'''return''' j & ((1 << power) - 1)<br />
'''T''' getHat('''int''' j):<br />
<font color=green>// Вернуть элемент HAT. Нет проверки на выход за пределы массива.</font><br />
'''return''' top[topIndex(j)][leafIndex(j)]<br />
*<br />
Рассмотрим как происходит вычисление адреса на примере. Пусть у нас есть HAT с размером листа равным <tex>4</tex>, тогда для нашего случая <tex>power = 2</tex>. Получим значения функций для элемента под номером <tex>5</tex>: <br />
*<tex>topIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен операции деления (взятию по модулю) <tex>j</tex> на <tex>2^{2}</tex>. То есть получим <tex>1</tex> {{---}} действительно элемент под номером <tex>5</tex> находится в первом листе (нумерация листов с <tex>0</tex>).<br />
*<tex>leafIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен умножению <tex>1</tex> на <tex>2^{2}</tex>. То есть после вычитания <tex>1</tex> получим число формата <tex>011..11</tex>, в нашем случае {{---}} <tex>011</tex>. Формула для <tex>leafIndex</tex> справедлива, так как элементы, которые находятся в разных листьях и различаются на <tex>2^k</tex>, будут иметь одинаковую позицию в этих листах, а младшие <tex>k</tex> бит у них будут общими. Поэтому сделаем операцию побитвое "и" к запрашиваемому индексу и к <tex> 2^k - 1 </tex> и получим нужный индекс в массиве <tex> leaf </tex>.<br />
<tex>5_{10} = 101_2</tex>, следовательно, <tex>101</tex> <tex>\&</tex> <tex>011 = 001</tex>, то есть индекс в листе равен <tex>1</tex> (в листах нумерация тоже с <tex>0</tex>).<br />
<br />
[[Файл:fullHAT.png|200px]]<br />
<br />
===Добавление элементов===<br />
*Чаще всего при добавлении элемента в одном из листьев (последнем незаполненном на данный момент) найдется свободное место, что позволит осуществить быструю вставку {{---}} <tex>O(1)</tex>. <br />
*Реже мы столкнемся со случаем, когда необходимо создать новый лист. Достаточно всего лишь добавить указатель в свободную ячейку главного массива, что также позволит произвести вставку элемента за <tex>O(1)</tex>.<br />
*Самый интересный случай {{---}} когда главный массив и все листья заполнены. Cначала вычислим нужный размер (массивы <tex>top</tex> и <tex>leaf</tex> увеличиваются в <tex>2</tex> раза, то есть <tex>power = power \cdot 2 </tex>), затем скопируем элементы в новую структуру HAT, освобождая старые листья и распределяя новые листья(размер листа изменился, а значит количество элементов в листе и количество используемых листьев так же изменится).<br />
Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивов переменной длины, потому что увеличения размеров всех массивов происходит редко (как будет видно ниже). Копировать элементы мы будем только тогда, когда главный массив полон (достигли соответствующей степени двойки, то есть <tex> N = (2 \cdot 2)^k</tex>, где <tex>k</tex> {{---}} натуральное число), тогда общая сумма перекопирования будет равна <tex>1+4+16+64+256+...+N</tex>. Воспользуемся тождеством: <tex>(x^{n+1} -1)=(x-1)(1+x+x^2+x^3+... + x^k)</tex>, тогда для нашего случая: <tex>1 +4+4^2+4^3+...+4^k = (4^{k+1} -1)/(4-1) = (4N-1)/3</tex>, или около <tex>4N/3</tex>. Это означает, что среднее число дополнительных операций копирования {{---}} <tex>O(N)</tex> для последовательного добавления <tex> N </tex> элементов, а не <tex>O(N^2)</tex>. Мы получили <tex>4N/3</tex> против <tex>2N</tex> в обычном динамическом массиве, то есть константа уменьшилась.<br />
<br />
[[Файл:AlgoF2.gif|400px]]<br />
<br />
===Расход памяти===<br />
HAT использует меньше дополнительной памяти, чем в стандартных подходах к расширению массивов, то есть полном перекопировании и перераспределении всего массива.<br />
Затраты дополнительной памяти (уже выделенной, но еще не используемой) в самом плохом случае {{---}} <tex>(top+leaf-1) ~= 2\sqrt{N} = O(\sqrt{N})</tex> (этот случай при пустой HAT {{---}} в <tex>top</tex> один указатель на единственный пустой лист). <br />
<br />
Если в листе будет <tex>power/2</tex> элементов, то ожидаемая трата дополнительной памяти уменьшается до <tex>(top + leaf/2) \approx 1.5\sqrt{N}</tex>. Таким образом HAT использует <tex>\Theta(\sqrt{N})</tex> дополнительной памяти. Это лучше [[Динамический массив |динамического массива]], который использует <tex>O(N)</tex> дополнительной памяти сразу после перекопирования элементов, и лучше [[Список | списка]].<br />
<br />
==Эффективность==<br />
Благодаря тому, что копирования в HAT происходят реже, чем в других реализациях динамических массивов, и в худшем случае требуется <tex>O(\sqrt{N})</tex> памяти, ее можно использовать в любых программах, требующих работу с массивами переменной длинны, где использование других структур данных (например списков) не удобно. На многих алгоритмах HAT работает значительно быстрее стандартных массивов, дополнительно можно ознакомиться с результатами некоторых тестов<ref>[http://pmg.org.ru/ai/tree_hash.htm Результаты тестов]</ref>.<br />
<br />
== Примечания ==<br />
<references/><br />
<br />
==Источники информации==<br />
*[[wikipedia:en:Hashed array tree | Wikipedia {{---}} Hashed array tree ]]<br />
*Cline, M.P. and G.A. Lomow, C++ FAQs, Reading, MA: Addison-Wesley, 1995. <br />
*Cormen, T.H., C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms, Cambridge, MA: MIT Press, 1990.<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Амортизационный анализ]]<br />
[[Категория:Структуры данных]]</div>Arthuriihttp://neerc.ifmo.ru/wiki/index.php?title=Hashed_Array_Tree&diff=71732Hashed Array Tree2019-07-10T14:27:49Z<p>Arthurii: Поправка орфографии.</p>
<hr />
<div>'''HAT (Hashed Array Tree)''' {{---}} структура данных, объединяющая в себе некоторые возможности массивов, хэш-таблиц и деревьев. Внешне структура похожа на хеш-таблицу с разрешением коллизий методом цепочек, отсюда и название. В действительности HAT {{---}} это эффективный способ реализовать массивы переменной длины, так как он предлагает хорошую производительность порядка <tex>O(N)</tex>, чтобы добавить <tex>N</tex> элементов к пустому массиву, и требует всего лишь <tex>O(\sqrt{N})</tex> дополнительной памяти. <br />
<br />
==Значимость==<br />
Массивы переменной длины {{---}} наиболее естественная и удобная структура данных для многих приложений, так как они обеспечивают постоянное время доступа к их элементам. Однако при их реализации мы можем столкнуться с двумя основными проблемами: чрезмерное копирование элементов и использование памяти. HAT {{---}} реализация массива переменной длины, решающая обе проблемы и предоставляющая ряд преимуществ по сравнению со стандартными реализациями.<br />
<br />
==Описание структуры==<br />
HAT состоит из главного массива указателей <tex>top</tex> и ряда листьев <tex>leaf</tex> (так же одномерные массивы), в которых хранятся элементы.<br />
Возможное число указателей в главном массиве и возможное число элементов в каждом листе равны между собой и являются степенями двойки. HAT заполняется элементами от самого малого листа к самому большому, при этом каждый лист заполняется слева направо.<br />
===Получение элемента по номеру===<br />
Благодаря использованию степеней двойки, мы можем эффективно находить элементы в HAT, используя поразрядные операции. Пусть размер главного массива и каждого листа будет равен <tex>2^{power}</tex>.<br />
'''int''' topIndex('''int''' j):<br />
<font color=green>// Получить номер указателя в основном массиве</font><br />
'''return''' j >> power<br />
'''int''' leafIndex('''int''' j):<br />
<font color=green>// Получить номер листа</font><br />
'''return''' j & ((1 << power) - 1)<br />
'''T''' getHat('''int''' j):<br />
<font color=green>// Вернуть элемент HAT. Нет проверки на выход за пределы массива.</font><br />
'''return''' top[topIndex(j)][leafIndex(j)]<br />
*<br />
Рассмотрим как происходит вычисление адреса на примере. Пусть у нас есть HAT с размером листа равным <tex>4</tex>, тогда для нашего случая <tex>power = 2</tex>. Получим значения функций для элемента под номером <tex>5</tex>: <br />
*<tex>topIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен операции деления (взятию по модулю) <tex>j</tex> на <tex>2^{2}</tex>. То есть получим <tex>1</tex> {{---}} действительно элемент под номером <tex>5</tex> находится в первом листе (нумерация листов с <tex>0</tex>).<br />
*<tex>leafIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен умножению <tex>1</tex> на <tex>2^{2}</tex>. То есть после вычитания <tex>1</tex> получим число формата <tex>011..11</tex>, в нашем случае {{---}} <tex>011</tex>. Формула для <tex>leafIndex</tex> справедлива, так как элементы, которые находятся в разных листьях и различаются на <tex>2^k</tex>, будут иметь одинаковую позицию в этих листах, а младшие <tex>k</tex> бит у них будут общими. Поэтому сделаем операцию побитвое "и" к запрашиваемому индексу и к <tex> 2^k - 1 </tex> и получим нужный индекс в массиве <tex> leaf </tex>.<br />
<tex>5_{10} = 101_2</tex> , следовательно <tex>101</tex> <tex>\&</tex> <tex>011 = 001</tex>, то есть индекс в листе равен <tex>1</tex> (в листах нумерация тоже с <tex>0</tex>).<br />
<br />
[[Файл:fullHAT.png|200px]]<br />
<br />
===Добавление элементов===<br />
*Чаще всего при добавлении элемента в одном из листьев (последнем незаполненном на данный момент) найдется свободное место, что позволит осуществить быструю вставку {{---}} <tex>O(1)</tex>. <br />
*Реже мы столкнемся со случаем, когда необходимо создать новый лист. Достаточно всего лишь добавить указатель в свободную ячейку главного массива, что также позволит произвести вставку элемента за <tex>O(1)</tex>.<br />
*Самый интересный случай {{---}} когда главный массив и все листья заполнены. Cначала вычислим нужный размер (массивы <tex>top</tex> и <tex>leaf</tex> увеличиваются в <tex>2</tex> раза, то есть <tex>power = power \cdot 2 </tex>), затем скопируем элементы в новую структуру HAT, освобождая старые листья и распределяя новые листья(размер листа изменился, а значит количество элементов в листе и количество используемых листьев так же изменится).<br />
Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивов переменной длины, потому что увеличения размеров всех массивов происходит редко (как будет видно ниже). Копировать элементы мы будем только тогда, когда главный массив полон (достигли соответствующей степени двойки, то есть <tex> N = (2 \cdot 2)^k</tex>, где <tex>k</tex> {{---}} натуральное число), тогда общая сумма перекопирования будет равна <tex>1+4+16+64+256+...+N</tex>. Воспользуемся тождеством: <tex>(x^{n+1} -1)=(x-1)(1+x+x^2+x^3+... + x^k)</tex>, тогда для нашего случая: <tex>1 +4+4^2+4^3+...+4^k = (4^{k+1} -1)/(4-1) = (4N-1)/3</tex>, или около <tex>4N/3</tex>. Это означает, что среднее число дополнительных операций копирования {{---}} <tex>O(N)</tex> для последовательного добавления <tex> N </tex> элементов, а не <tex>O(N^2)</tex>. Мы получили <tex>4N/3</tex> против <tex>2N</tex> в обычном динамическом массиве, то есть константа уменьшилась.<br />
<br />
[[Файл:AlgoF2.gif|400px]]<br />
<br />
===Расход памяти===<br />
HAT использует меньше дополнительной памяти, чем в стандартных подходах к расширению массивов, то есть полном перекопировании и перераспределении всего массива.<br />
Затраты дополнительной памяти (уже выделенной, но еще не используемой) в самом плохом случае {{---}} <tex>(top+leaf-1) ~= 2\sqrt{N} = O(\sqrt{N})</tex> (этот случай при пустой HAT {{---}} в <tex>top</tex> один указатель на единственный пустой лист). <br />
<br />
Если в листе будет <tex>power/2</tex> элементов, то ожидаемая трата дополнительной памяти уменьшается до <tex>(top + leaf/2) \approx 1.5\sqrt{N}</tex>. Таким образом HAT использует <tex>\Theta(\sqrt{N})</tex> дополнительной памяти. Это лучше [[Динамический массив |динамического массива]], который использует <tex>O(N)</tex> дополнительной памяти сразу после перекопирования элементов, и лучше [[Список | списка]].<br />
<br />
==Эффективность==<br />
Благодаря тому, что копирования в HAT происходят реже, чем в других реализациях динамических массивов, и в худшем случае требуется <tex>O(\sqrt{N})</tex> памяти, ее можно использовать в любых программах, требующих работу с массивами переменной длинны, где использование других структур данных (например списков) не удобно. На многих алгоритмах HAT работает значительно быстрее стандартных массивов, дополнительно можно ознакомиться с результатами некоторых тестов<ref>[http://pmg.org.ru/ai/tree_hash.htm Результаты тестов]</ref>.<br />
<br />
== Примечания ==<br />
<references/><br />
<br />
==Источники информации==<br />
*[[wikipedia:en:Hashed array tree | Wikipedia {{---}} Hashed array tree ]]<br />
*Cline, M.P. and G.A. Lomow, C++ FAQs, Reading, MA: Addison-Wesley, 1995. <br />
*Cormen, T.H., C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms, Cambridge, MA: MIT Press, 1990.<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Амортизационный анализ]]<br />
[[Категория:Структуры данных]]</div>Arthuriihttp://neerc.ifmo.ru/wiki/index.php?title=Hashed_Array_Tree&diff=71731Hashed Array Tree2019-07-10T14:27:15Z<p>Arthurii: Поправка грамматики.</p>
<hr />
<div>'''HAT (Hashed Array Tree)''' {{---}} структура данных, объединяющая в себе некоторые возможности массивов, хэш-таблиц и деревьев. Внешне структура похожа на хеш-таблицу с разрешением коллизий методом цепочек, отсюда и название. В действительности HAT {{---}} это эффективный способ реализовать массивы переменной длины, так как он предлагает хорошую производительность порядка <tex>O(N)</tex>, чтобы добавить <tex>N</tex> элементов к пустому массиву, и требует всего лишь <tex>O(\sqrt{N})</tex> дополнительной памяти. <br />
<br />
==Значимость==<br />
Массивы переменной длины {{---}} наиболее естественная и удобная структура данных для многих приложений, так как они обеспечивают постоянное время доступа к их элементам. Однако при их реализации мы можем столкнуться с двумя основными проблемами: чрезмерное копирование элементов и использование памяти. HAT {{---}} реализация массива переменной длины, решающая обе проблемы и предоставляющая ряд преимуществ по сравнению со стандартными реализациями.<br />
<br />
==Описание структуры==<br />
HAT состоит из главного массива указателей <tex>top</tex> и ряда листьев <tex>leaf</tex> (так же одномерные массивы), в которых хранятся элементы.<br />
Возможное число указателей в главном массиве и возможное число элементов в каждом листе равны между собой и являются степенями двойки. HAT заполняется элементами от самого малого листа к самому большому, при этом каждый лист заполняется слева направо.<br />
===Получение элемента по номеру===<br />
Благодаря использованию степеней двойки, мы можем эффективно находить элементы в HAT, используя поразрядные операции. Пусть размер главного массива и каждого листа будет равен <tex>2^{power}</tex>.<br />
'''int''' topIndex('''int''' j):<br />
<font color=green>// Получить номер указателя в основном массиве</font><br />
'''return''' j >> power<br />
'''int''' leafIndex('''int''' j):<br />
<font color=green>// Получить номер листа</font><br />
'''return''' j & ((1 << power) - 1)<br />
'''T''' getHat('''int''' j):<br />
<font color=green>// Вернуть элемент HAT. Нет проверки на выход за пределы массива.</font><br />
'''return''' top[topIndex(j)][leafIndex(j)]<br />
*<br />
Рассмотрим как происходит вычисление адреса на примере. Пусть у нас есть HAT с размером листа равным <tex>4</tex>, тогда для нашего случая <tex>power = 2</tex>. Получим значения функций для элемента под номером <tex>5</tex>: <br />
*<tex>topIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен операции деления (взятию по модулю) <tex>j</tex> на <tex>2^{2}</tex>. То есть получим <tex>1</tex> {{---}} действительно элемент под номером <tex>5</tex> находится в первом листе (нумерация листов с <tex>0</tex>).<br />
*<tex>leafIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен умножению <tex>1</tex> на <tex>2^{2}</tex>. То есть после вычитания <tex>1</tex> получим число формата <tex>011..11</tex>, в нашем случае {{---}} <tex>011</tex>. Формула для <tex>leafIndex</tex> справедлива, так как элементы, которые находятся в разных листьях и различаются на <tex>2^k</tex>, будут иметь одинаковую позицию в этих листах, а младшие <tex>k</tex> бит у них будут общими. Поэтому сделаем операцию побивое "и" к запрашиваему индексу и к <tex> 2^k - 1 </tex> и получим нужный индекс в массиве <tex> leaf </tex>.<br />
<tex>5_{10} = 101_2</tex> , следовательно <tex>101</tex> <tex>\&</tex> <tex>011 = 001</tex>, то есть индекс в листе равен <tex>1</tex> (в листах нумерация тоже с <tex>0</tex>).<br />
<br />
[[Файл:fullHAT.png|200px]]<br />
<br />
===Добавление элементов===<br />
*Чаще всего при добавлении элемента в одном из листьев (последнем незаполненном на данный момент) найдется свободное место, что позволит осуществить быструю вставку {{---}} <tex>O(1)</tex>. <br />
*Реже мы столкнемся со случаем, когда необходимо создать новый лист. Достаточно всего лишь добавить указатель в свободную ячейку главного массива, что также позволит произвести вставку элемента за <tex>O(1)</tex>.<br />
*Самый интересный случай {{---}} когда главный массив и все листья заполнены. Cначала вычислим нужный размер (массивы <tex>top</tex> и <tex>leaf</tex> увеличиваются в <tex>2</tex> раза, то есть <tex>power = power \cdot 2 </tex>), затем скопируем элементы в новую структуру HAT, освобождая старые листья и распределяя новые листья(размер листа изменился, а значит количество элементов в листе и количество используемых листьев так же изменится).<br />
Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивов переменной длины, потому что увеличения размеров всех массивов происходит редко (как будет видно ниже). Копировать элементы мы будем только тогда, когда главный массив полон (достигли соответствующей степени двойки, то есть <tex> N = (2 \cdot 2)^k</tex>, где <tex>k</tex> {{---}} натуральное число), тогда общая сумма перекопирования будет равна <tex>1+4+16+64+256+...+N</tex>. Воспользуемся тождеством: <tex>(x^{n+1} -1)=(x-1)(1+x+x^2+x^3+... + x^k)</tex>, тогда для нашего случая: <tex>1 +4+4^2+4^3+...+4^k = (4^{k+1} -1)/(4-1) = (4N-1)/3</tex>, или около <tex>4N/3</tex>. Это означает, что среднее число дополнительных операций копирования {{---}} <tex>O(N)</tex> для последовательного добавления <tex> N </tex> элементов, а не <tex>O(N^2)</tex>. Мы получили <tex>4N/3</tex> против <tex>2N</tex> в обычном динамическом массиве, то есть константа уменьшилась.<br />
<br />
[[Файл:AlgoF2.gif|400px]]<br />
<br />
===Расход памяти===<br />
HAT использует меньше дополнительной памяти, чем в стандартных подходах к расширению массивов, то есть полном перекопировании и перераспределении всего массива.<br />
Затраты дополнительной памяти (уже выделенной, но еще не используемой) в самом плохом случае {{---}} <tex>(top+leaf-1) ~= 2\sqrt{N} = O(\sqrt{N})</tex> (этот случай при пустой HAT {{---}} в <tex>top</tex> один указатель на единственный пустой лист). <br />
<br />
Если в листе будет <tex>power/2</tex> элементов, то ожидаемая трата дополнительной памяти уменьшается до <tex>(top + leaf/2) \approx 1.5\sqrt{N}</tex>. Таким образом HAT использует <tex>\Theta(\sqrt{N})</tex> дополнительной памяти. Это лучше [[Динамический массив |динамического массива]], который использует <tex>O(N)</tex> дополнительной памяти сразу после перекопирования элементов, и лучше [[Список | списка]].<br />
<br />
==Эффективность==<br />
Благодаря тому, что копирования в HAT происходят реже, чем в других реализациях динамических массивов, и в худшем случае требуется <tex>O(\sqrt{N})</tex> памяти, ее можно использовать в любых программах, требующих работу с массивами переменной длинны, где использование других структур данных (например списков) не удобно. На многих алгоритмах HAT работает значительно быстрее стандартных массивов, дополнительно можно ознакомиться с результатами некоторых тестов<ref>[http://pmg.org.ru/ai/tree_hash.htm Результаты тестов]</ref>.<br />
<br />
== Примечания ==<br />
<references/><br />
<br />
==Источники информации==<br />
*[[wikipedia:en:Hashed array tree | Wikipedia {{---}} Hashed array tree ]]<br />
*Cline, M.P. and G.A. Lomow, C++ FAQs, Reading, MA: Addison-Wesley, 1995. <br />
*Cormen, T.H., C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms, Cambridge, MA: MIT Press, 1990.<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
[[Категория:Амортизационный анализ]]<br />
[[Категория:Структуры данных]]</div>Arthuriihttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2&diff=71730Динамический массив2019-07-10T14:23:16Z<p>Arthurii: Поправка орфографии.</p>
<hr />
<div>{{Определение<br />
| definition =<br />
'''Массив''' {{---}} набор однотипных переменных, доступ к которым осуществляется по индексу. '''Динамический массив''' может изменять свой размер в зависимости от количества элементов в нём.<br />
}}<br />
<br />
== Операции ==<br />
Определим операции, которые мы будем применять к динамическому массиву:<br><br />
=== get(i) ===<br />
:Возвращает значение <tex>i</tex>-ой ячейки массива. Время выполнения {{---}} <tex>O(1)</tex>.<br />
=== set(i,x) ===<br />
:В <tex>i</tex>-ую ячейку массива записывается элемент <tex>x</tex>. Время выполнения {{---}} <tex>O(1)</tex>.<br />
=== add(x) ===<br />
:Добавление в массив элемента <tex>x</tex>. Время выполнения {{---}} <tex>O(1)</tex>; в худшем случае, при котором необходимо перенести все элементы из текущего массива во вдвое больший массив {{---}} <tex>O(n)</tex> (<tex>n</tex> {{---}} размер массива).<br />
=== del() ===<br />
:Удаляет последний элемент массива. В случае, если количество элементов в массиве в <tex>C</tex> раз меньше его длины, то происходит сжатие в <tex>B</tex> раз. (<tex>C,B</tex> {{---}} константы, зависящие от реализации). Время выполнения операции в худшем случае {{---}} <tex>O(n)</tex>.<br />
<br />
=== size() ===<br />
:Возвращает количество элементов массива. Время выполнения {{---}} <tex>O(1)</tex>.<br />
<br />
== Амортизационная стоимость каждой операции ==<br />
Пусть наш массив расширяется в <tex>2</tex> раза, и уменьшается в <tex>2</tex> раза, когда длина массива в <tex>4</tex> раза больше количества элементов в массиве. В этом случае амортизационная стоимость каждой операции будет <tex>O(1)</tex>.<br />
=== Метод предоплаты ===<br />
==== Стоимость операции add(x) ====<br />
[[Файл:Безымянный1.png|400px|thumb|right|Иллюстрация]]<br />
Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции '''add(x)''', при которой нам не требуется копирование, мы будем использовать три монетки. Из них одна пойдёт на стоимость самой этой операции, а две будут в резерве (пусть, если мы добавили <tex>i</tex>-ый элемент, мы будем класть по одной монетке к элементам с номерами <tex dpi=150>i</tex> и <tex dpi=150>i-\frac{n}{2}</tex>). В итоге, к тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которую мы и можем использовать на его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции '''add(x)''' {{---}} <tex>3</tex>, и среднее время её работы {{---}} <tex>O(1)</tex>.<br />
==== Стоимость операции del() ====<br />
При каждой операции будем использовать две монетки. Одну из них потратим на само удаление элемента, другую на элемент, стоящий на позиции <tex>i \bmod \dfrac{n}{4}</tex>. Тогда даже в самом худшем случае (только что расширились, а потом <tex>\dfrac{n}{4}</tex> удалили) у каждого элемента из первых <tex>\dfrac{n}{4}</tex> будет по монете и на удаление надо будет потратить только <tex>1</tex> монету.<br />
<br />
=== Метод потенциалов ===<br />
За потенциал примем число:<br />
<tex dpi=150>\Phi(c, s) = \begin{cases}<br />
2s-c, & \text{if } s\geqslant\frac{1}{2}c \\<br />
\frac{1}{2}c-s, & \text{if } s<\frac{1}{2}c<br />
\end{cases}</tex>, где <tex>c</tex> {{---}} размер массива, <tex>s</tex> {{---}} число элементов массива.<br />
<br />
==== Стоимость операции '''add(x)''' ====<br />
<br />
* <tex dpi=150>\frac{s}{c} = 1</tex>, массив расширяется: <tex dpi=150> a_i = t_i + \Phi(2c, s + 1) - \Phi(c, s) = (s + 1) + (2(s+1)-2c)-(2s-c) = 3 </tex><br />
<br />
* <tex dpi=150>1>\frac{s}{c}\geqslant\frac{1}{2}</tex>, массив не расширяется: <tex dpi=150>a_i=t_i+\Phi(c,s+1)-\Phi(c,s)=1+(2(s+1)-c)-(2s-c)=3</tex><br />
<br />
* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s+1}{c}\geqslant\frac{1}{2}</tex>, массив не расширяется:<br />
<tex dpi=150>a_i = t_i + \Phi(c, s+1)-\Phi(c, s)= 1 +(2(s+1)-c)-(\frac{1}{2}c - s)= 3+3s-\frac{3}{2}c= 3 + \frac{s}{c}3c-\frac{3}{2}c <3+\frac{3}{2}c-\frac{3}{2}c=3</tex><br />
<br />
* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s+1}{c}<\frac{1}{2}</tex>, массив не расширяется: <tex dpi=150>a_i = t_i + \Phi(c, s + 1) - \Phi(c, s) = 1 + (\frac{1}{2}c - (s + 1)) - (\frac{1}{2}c - s) = 0</tex><br />
<br />
В итоге, средняя стоимость операции {{---}} <tex>3</tex>, а среднее время работы {{---}} <tex>O(1)</tex>.<br />
<br />
==== Стоимость операции del() ====<br />
<br />
* <tex dpi=150>\frac{s}{c}=\frac{1}{4}</tex>, массив сужается: <tex dpi=150>a_i = t_i + \Phi(\frac{c}{2}, s - 1) - \Phi(c, s) = s + (\frac{1}{2}\cdot\frac{1}{2}c-(s-1)) - (\frac{1}{2}c-s) = 1-\frac{1}{4}c+s=1</tex><br />
* <tex dpi=150>\frac{1}{4}<\frac{s}{c}<\frac{1}{2}</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (\frac{1}{2}c-(s-1))-(\frac{1}{2}c-s)= 2</tex><br />
* <tex dpi=150>\frac{s}{c}\geqslant\frac{1}{2}, \frac{s-1}{c}<\frac{1}{2}\Rightarrow s=\frac{1}{2}c</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) =1 +(\frac{1}{2}c-(s-1))-(2s-c)=2+\frac{3}{2}c-3s = 2</tex><br />
* <tex dpi=150>\frac{s}{c}>\frac{1}{2}</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (2(s-1)-c)-(2s-c)=0</tex><br />
<br />
Средняя стоимость операции {{---}} <tex>2</tex>, а среднее время работы {{---}} <tex>O(1)</tex>.<br />
<br />
==Динамические массивы в современных языках программирования==<br />
Динамические массивы широко применяются во многих языках программирования. Рассмотрим, как эта структура данных реализуется в С++ и Java. <br />
===С++ {{---}} vector===<br />
В С++ динамический массив используется в структуре vector, она описана в STL(<vector>). Стратегия расширения проста: при попытке записи в массив нового элемента в момент полного заполнения памяти происходит увеличение размера в <tex>2</tex> раза при компиляции GNU C++ и в <tex>1.5</tex> раза при компиляции Microsoft Visual C++. При удалении элементов уменьшение размера массива никогда не происходит. При инициализации vector по-умолчанию начальный размер равен <tex>0</tex>.<br />
===Java {{---}} ArrayList===<br />
В Java структура ArrayList основана на динамическом массиве. При превышении максимального на данный момент размера происходит увеличение в <tex>1.5</tex> раза. Причем начальный размер равен <tex>10</tex>. Как и в vector, в ArrayList не предусмотрено изменение размера при удалении элементов. Для принудительного изменения размера следует использовать метод trimToSize().<br />
<br />
==Источники информации==<br />
* [[wikipedia:Dynamic_array | Wikipedia {{---}} Dynamic array]]<br />
* [[wikipedia:ru:Динамический_массив | Wikipedia {{---}} Динамический массив]]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Амортизационный анализ]]</div>Arthuriihttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2&diff=71729Динамический массив2019-07-10T14:22:07Z<p>Arthurii: Поправка пунктуации.</p>
<hr />
<div>{{Определение<br />
| definition =<br />
'''Массив''' {{---}} набор однотипных переменных, доступ к которым осуществляется по индексу. '''Динамический массив''' может изменять свой размер в зависимости от количества элементов в нём.<br />
}}<br />
<br />
== Операции ==<br />
Определим операции, которые мы будем применять к динамическому массиву:<br><br />
=== get(i) ===<br />
:Возвращает значение <tex>i</tex>-ой ячейки массива. Время выполнения {{---}} <tex>O(1)</tex>.<br />
=== set(i,x) ===<br />
:В <tex>i</tex>-ую ячейку массива записывается элемент <tex>x</tex>. Время выполнения {{---}} <tex>O(1)</tex>.<br />
=== add(x) ===<br />
:Добавление в массив элемента <tex>x</tex>. Время выполнения {{---}} <tex>O(1)</tex>; в худшем случае, при котором необходимо перенести все элементы из текущего массива в вдвое больший массив {{---}} <tex>O(n)</tex> (<tex>n</tex> {{---}} размер массива).<br />
=== del() ===<br />
:Удаляет последний элемент массива. В случае, если количество элементов в массиве в <tex>C</tex> раз меньше его длины, то происходит сжатие в <tex>B</tex> раз. (<tex>C,B</tex> {{---}} константы, зависящие от реализации). Время выполнения операции в худшем случае {{---}} <tex>O(n)</tex>.<br />
<br />
=== size() ===<br />
:Возвращает количество элементов массива. Время выполнения {{---}} <tex>O(1)</tex>.<br />
<br />
== Амортизационная стоимость каждой операции ==<br />
Пусть наш массив расширяется в <tex>2</tex> раза, и уменьшается в <tex>2</tex> раза, когда длина массива в <tex>4</tex> раза больше количества элементов в массиве. В этом случае амортизационная стоимость каждой операции будет <tex>O(1)</tex>.<br />
=== Метод предоплаты ===<br />
==== Стоимость операции add(x) ====<br />
[[Файл:Безымянный1.png|400px|thumb|right|Иллюстрация]]<br />
Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции '''add(x)''', при которой нам не требуется копирование, мы будем использовать три монетки. Из них одна пойдёт на стоимость самой этой операции, а две будут в резерве (пусть, если мы добавили <tex>i</tex>-ый элемент, мы будем класть по одной монетке к элементам с номерами <tex dpi=150>i</tex> и <tex dpi=150>i-\frac{n}{2}</tex>). В итоге, к тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которую мы и можем использовать на его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции '''add(x)''' {{---}} <tex>3</tex>, и среднее время её работы {{---}} <tex>O(1)</tex>.<br />
==== Стоимость операции del() ====<br />
При каждой операции будем использовать две монетки. Одну из них потратим на само удаление элемента, другую на элемент, стоящий на позиции <tex>i \bmod \dfrac{n}{4}</tex>. Тогда даже в самом худшем случае (только что расширились, а потом <tex>\dfrac{n}{4}</tex> удалили) у каждого элемента из первых <tex>\dfrac{n}{4}</tex> будет по монете и на удаление надо будет потратить только <tex>1</tex> монету.<br />
<br />
=== Метод потенциалов ===<br />
За потенциал примем число:<br />
<tex dpi=150>\Phi(c, s) = \begin{cases}<br />
2s-c, & \text{if } s\geqslant\frac{1}{2}c \\<br />
\frac{1}{2}c-s, & \text{if } s<\frac{1}{2}c<br />
\end{cases}</tex>, где <tex>c</tex> {{---}} размер массива, <tex>s</tex> {{---}} число элементов массива.<br />
<br />
==== Стоимость операции '''add(x)''' ====<br />
<br />
* <tex dpi=150>\frac{s}{c} = 1</tex>, массив расширяется: <tex dpi=150> a_i = t_i + \Phi(2c, s + 1) - \Phi(c, s) = (s + 1) + (2(s+1)-2c)-(2s-c) = 3 </tex><br />
<br />
* <tex dpi=150>1>\frac{s}{c}\geqslant\frac{1}{2}</tex>, массив не расширяется: <tex dpi=150>a_i=t_i+\Phi(c,s+1)-\Phi(c,s)=1+(2(s+1)-c)-(2s-c)=3</tex><br />
<br />
* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s+1}{c}\geqslant\frac{1}{2}</tex>, массив не расширяется:<br />
<tex dpi=150>a_i = t_i + \Phi(c, s+1)-\Phi(c, s)= 1 +(2(s+1)-c)-(\frac{1}{2}c - s)= 3+3s-\frac{3}{2}c= 3 + \frac{s}{c}3c-\frac{3}{2}c <3+\frac{3}{2}c-\frac{3}{2}c=3</tex><br />
<br />
* <tex dpi=150>\frac{s}{c}<\frac{1}{2}, \frac{s+1}{c}<\frac{1}{2}</tex>, массив не расширяется: <tex dpi=150>a_i = t_i + \Phi(c, s + 1) - \Phi(c, s) = 1 + (\frac{1}{2}c - (s + 1)) - (\frac{1}{2}c - s) = 0</tex><br />
<br />
В итоге, средняя стоимость операции {{---}} <tex>3</tex>, а среднее время работы {{---}} <tex>O(1)</tex>.<br />
<br />
==== Стоимость операции del() ====<br />
<br />
* <tex dpi=150>\frac{s}{c}=\frac{1}{4}</tex>, массив сужается: <tex dpi=150>a_i = t_i + \Phi(\frac{c}{2}, s - 1) - \Phi(c, s) = s + (\frac{1}{2}\cdot\frac{1}{2}c-(s-1)) - (\frac{1}{2}c-s) = 1-\frac{1}{4}c+s=1</tex><br />
* <tex dpi=150>\frac{1}{4}<\frac{s}{c}<\frac{1}{2}</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (\frac{1}{2}c-(s-1))-(\frac{1}{2}c-s)= 2</tex><br />
* <tex dpi=150>\frac{s}{c}\geqslant\frac{1}{2}, \frac{s-1}{c}<\frac{1}{2}\Rightarrow s=\frac{1}{2}c</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) =1 +(\frac{1}{2}c-(s-1))-(2s-c)=2+\frac{3}{2}c-3s = 2</tex><br />
* <tex dpi=150>\frac{s}{c}>\frac{1}{2}</tex>, массив не сужается: <tex dpi=150>a_i = t_i + \Phi(c, s - 1) - \Phi(c, s) = 1 + (2(s-1)-c)-(2s-c)=0</tex><br />
<br />
Средняя стоимость операции {{---}} <tex>2</tex>, а среднее время работы {{---}} <tex>O(1)</tex>.<br />
<br />
==Динамические массивы в современных языках программирования==<br />
Динамические массивы широко применяются во многих языках программирования. Рассмотрим, как эта структура данных реализуется в С++ и Java. <br />
===С++ {{---}} vector===<br />
В С++ динамический массив используется в структуре vector, она описана в STL(<vector>). Стратегия расширения проста: при попытке записи в массив нового элемента в момент полного заполнения памяти происходит увеличение размера в <tex>2</tex> раза при компиляции GNU C++ и в <tex>1.5</tex> раза при компиляции Microsoft Visual C++. При удалении элементов уменьшение размера массива никогда не происходит. При инициализации vector по-умолчанию начальный размер равен <tex>0</tex>.<br />
===Java {{---}} ArrayList===<br />
В Java структура ArrayList основана на динамическом массиве. При превышении максимального на данный момент размера происходит увеличение в <tex>1.5</tex> раза. Причем начальный размер равен <tex>10</tex>. Как и в vector, в ArrayList не предусмотрено изменение размера при удалении элементов. Для принудительного изменения размера следует использовать метод trimToSize().<br />
<br />
==Источники информации==<br />
* [[wikipedia:Dynamic_array | Wikipedia {{---}} Dynamic array]]<br />
* [[wikipedia:ru:Динамический_массив | Wikipedia {{---}} Динамический массив]]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Амортизационный анализ]]</div>Arthuriihttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BC%D0%BE%D1%80%D1%82%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7&diff=71728Амортизационный анализ2019-07-10T14:15:32Z<p>Arthurii: Поправка пунктуации. ("следовательно" здесь - вводное слово, а не союз)</p>
<hr />
<div>==Основные определения==<br />
{{Определение | definition =<br />
'''Амортизационный анализ''' (англ. ''amortized analysis'') {{---}} метод подсчёта времени, требуемого для выполнения последовательности операций над структурой данных. При этом время усредняется по всем выполняемым операциям, и анализируется средняя производительность операций в худшем случае.<br />
}}<br />
Такой анализ чаще всего используется, чтобы показать, что даже если некоторые из операций последовательности являются дорогостоящими, то при усреднении по всем операциям средняя их стоимость будет небольшой за счёт низкой частоты встречаемости. Подчеркнём, что оценка, даваемая амортизационным анализом, не является вероятностной: это оценка среднего времени выполнения операций для худшего случая. <br />
{{Определение | definition =<br />
'''Средняя амортизационная стоимость операций''' {{---}} величина <tex>a</tex>, находящаяся по формуле: <tex dpi = 150>a = \genfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n}</tex>, где <tex>t_1,t_2 \dots t_n</tex> {{---}} время выполнения операций <tex>1,2 \dots n</tex>, совершённых над структурой данных.<br />
}}<br />
Амортизационный анализ использует следующие методы:<br />
#Метод усреднения (метод группового анализа).<br />
#Метод потенциалов.<br />
#Метод предоплаты (метод бухгалтерского учёта).<br />
<br />
==Метод усреднения==<br />
<br />
В методе усреднения амортизационная стоимость операций определяется напрямую по формуле, указанной выше: суммарная стоимость всех операций алгоритма делится на их количество.<br />
<br />
====Примеры====<br />
<br />
=====Стек с multipop=====<br />
<br />
Рассмотрим [[Стек | стек]] с операцией <tex>\mathrm{multipop}{(a)}</tex> {{---}} извлечение из стека <tex>a</tex> элементов. В худшем случае она работает за <tex>O(n)</tex> времени, если удаляются все элементы массива. Однако прежде чем удалить элемент, его нужно добавить в стек. Итак, если в стеке было не более <tex>n</tex> элементов, то в худшем случае с каждым из них могли быть произведены две операции {{---}} добавление в стек и извлечение из него. Например, если было <tex>n</tex> операций <tex>\mathrm{push}{}</tex> {{---}} добавление в стек, стоимость каждой <tex>O(1)</tex>, и одна операция <tex>\mathrm{multipop}{(n)}</tex>, то суммарное время всех операций {{---}} <tex>O(n)</tex>, всего операций <tex>n + 1</tex>, а значит, амортизационная стоимость операции {{---}} <tex>O(1)</tex>.<br />
<br />
Распишем приведённые рассуждения более формально.<br />
Пусть <tex>n</tex> {{---}} количество операций, <tex>m</tex> {{---}} количество элементов, задействованных в этих операциях. Очевидно, <tex>m \leqslant n</tex> Тогда:<br />
<br />
<tex dpi = "150">a = \genfrac{}{}{}{}{\sum\limits^{n}_{i=1} {t_i}}{n} = \genfrac{}{}{}{}{\sum\limits^{n}_{i=1} \sum\limits^{m}_{j=1} {t_{ij}}}{n} = \genfrac{}{}{}{}{\sum\limits^{m}_{j=1} \sum\limits^{n}_{i=1} {t_{ij}}}{n},</tex> где <tex>{t_{ij}}</tex> {{---}} стоимость <tex>i</tex>-ой операции над <tex>j</tex>-ым элементом. Величина <tex>\sum\limits^{n}_{i=1} {t_{ij}}</tex> не превосходит <tex>2</tex>, так как над элементом можно совершить только две операции, стоимость которых равна <tex>1</tex> {{---}} добавление и удаление. Тогда:<br />
<br />
<tex dpi = "150">a \leqslant \genfrac{}{}{}{}{2m}{n} \leqslant 2,</tex> так как <tex>m \leqslant n</tex>.<br />
<br />
Таким образом, средняя амортизационная стоимость операций <tex>a = O(1)</tex>.<br />
<br />
=====Двоичный счётчик=====<br />
Рассмотрим также двоичный инкрементальный счётчик (единственная возможная операция {{---}} увеличить значение на единицу). <br />
Пусть результат увеличения счётчика {{---}} <tex>n</tex>, тогда в худшем случае необходимо изменить значения <tex> 1 + \lfloor \log n \rfloor</tex> бит, и стоимость <tex>n</tex> операций составит <tex> O(n \log n) </tex>.<br />
Теперь воспользуемся для анализа методом усреднения.<br />
Каждый следующий бит изменяет своё значение в <tex dpi = "150">n, \genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{4} \dots</tex> операциях.<br />
Общая стоимость: <br />
<br />
<tex dpi = "150"> \sum\limits_{i=0}^{\lfloor \log n \rfloor} \genfrac{}{}{}{}{n}{2^i} < 2n = O(n)</tex><br />
<br />
В итоге амортизационная стоимость одной операции {{---}} <tex>O(1)</tex>.<br />
<br />
==Метод потенциалов==<br />
<br />
{{Теорема<br />
|about =<br />
О методе потенциалов<br />
|statement =<br />
Введём для каждого состояния структуры данных величину <tex>\Phi</tex> {{---}} потенциал. Изначально потенциал равен <tex>\Phi_0</tex>, а после выполнения <tex>i</tex>-й операции {{---}} <tex>\Phi_i</tex>. Стоимость <tex>i</tex>-й операции обозначим <tex>a_i = t_i + \Phi_i - \Phi_{i-1}</tex>. Пусть <tex>n</tex> {{---}} количество операций, <tex>m</tex> {{---}} размер структуры данных. Тогда средняя амортизационная стоимость операций <tex>a = O(f(n, m)),</tex> если выполнены два условия:<br />
<br />
#Для любого <tex>i: a_i = O(f(n, m))</tex><br />
#Для любого <tex>i: \Phi_i = O(n \cdot f(n, m))</tex><br />
|proof =<br />
<tex dpi = "150">a = \genfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n} = \genfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {a_i} + \sum\limits^{n - 1}_{i = 0} {\Phi_i} - \sum\limits^{n}_{i = 1} {\Phi_i} }{n} = \genfrac{}{}{}{}{n \cdot O(f(n, m)) + \Phi_0 - \Phi_n}{n} = O(f(n, m))</tex><br />
}}<br />
<br />
====Примеры====<br />
<br />
=====Стек с multipop=====<br />
В качестве примера вновь рассмотрим стек с операцией <tex>\mathrm{multipop}{(a)}</tex>. Пусть потенциал {{---}} это количество элементов в стеке. Тогда:<br />
<br />
# Амортизационная стоимость операций:<br />
#* <tex>a_{push} = 1 + 1 = 2,</tex> так как время выполнения операции <tex>\mathrm{push}{}</tex> {{---}} <tex>1</tex>, и изменение потенциала {{---}} тоже <tex>1</tex>.<br />
#* <tex>a_{pop} = 1 - 1 = 0,</tex> так как время выполнения операции <tex>\mathrm{pop}{}</tex> {{---}} <tex>1</tex>, а изменение потенциала {{---}} <tex>-1</tex>.<br />
#* <tex>a_{multipop} = k - k = 0,</tex> так как время выполнения операции <tex>\mathrm{multipop}{(k)}</tex> {{---}} <tex>k</tex>, а изменение потенциала {{---}} <tex>-k</tex>.<br />
# Для любого <tex>i: \Phi_i = O(n),</tex> так как элементов в стеке не может быть больше <tex>n</tex><br />
<br />
Таким образом, <tex>f(n, m) = 1</tex>, а значит, средняя амортизационная стоимость операций <tex>a = O(1)</tex>.<br />
<br />
=====Динамические хэш-таблицы=====<br />
<br />
Рассмотрим [[Хеш-таблица | хэш-таблицы]], использующие цепочки в виде [[Список | списков]] для [[Разрешение коллизий | разрешения коллизий]]. Для того, чтобы поиск элемента в цепочке не начал слишком сильно влиять на производительность, введём величину <tex> \alpha </tex> {{---}} фактор загруженности (load factor) нашей таблицы.<br />
Пусть в нашей таблице размером <tex> m </tex> хранится <tex> n </tex> элементов, тогда <tex dpi = "150"> \alpha = \genfrac{}{}{}{}{n}{m} </tex>.<br />
Введём значение <tex>\alpha_{max}</tex>, при превышении которого таблица будет пересоздана с увеличением размера в <tex> 2 </tex> раза, и все элементы будут перераспределены по-новому (rehashing).<br />
Из-за этого сложность операции <tex>\mathrm{add}</tex> в худшем случае составит <tex> O(n) </tex>.<br />
<br />
Для анализа структуры введём следующую потенциальную функцию: <tex>\Phi = 2n - \alpha_{max}m </tex><br />
<br />
Рассмотрим время работы каждой из операций <tex>\mathrm{add},\ \mathrm{remove},\ \mathrm{find}</tex>:<br />
#<tex>\mathrm{add}{}</tex>: <tex>\, n</tex> увеличивается на единицу. Следовательно, возникают два случая:<br />
#*<tex> \alpha < \alpha_{max} : \alpha_i = 1 + 2 \cdot (n + 1) - \alpha_{max} m - (2n - \alpha_{max} m) = 3</tex>, так как время выполнения операции <tex> \mathrm{add} </tex> {{---}} <tex> 1 </tex><br />
#*<tex>\alpha = \alpha_{max} : a_i = 1 + \alpha_{max}m + 2 \cdot (\alpha_{max} m + 1) - 2\alpha_{max} m - 2 \alpha_{max} m + \alpha_{max} m = 3 </tex>, так как таблица увеличивается в размере, поэтому время работы операции <tex> \mathrm{add} </tex> составит <tex> 1 + \alpha_{max}m </tex>, потому что сейчас в таблице <tex> n = \alpha_{max} m </tex> элементов.<br />
# <tex>\mathrm{find}{}</tex>:<br />
#* Если элементы распределяются по таблице достаточно равномерно, то время поиска элемента в списке {{---}} <tex>O(1)</tex>, потенциал не изменяется, следовательно, и реальная, и амортизированная сложности {{---}} <tex>1</tex>.<br />
#* В случае, если все элементы оказываются размещены в одном списке, время поиска элемента достигает <tex>O(n)</tex>. Это время может быть улучшено до <tex>O(\log n)</tex>, если вместо списков использовать сбалансированные [[Дерево поиска, наивная реализация | деревья поиска]] (эта модификация была добавлена в <tex>\mathrm{Java\ 8}{}</tex> для стандартной коллекции <tex>\mathrm{HashSet}</tex>).<br />
#<tex>\mathrm{remove}{}</tex>: <tex> n</tex> уменьшается на единицу. Тогда амортизационное время работы с учётом изменения потенциала составит:<br />
#* <tex> a_{remove} = 1 + 2 \cdot (n - 1) - \alpha_{max} m - (2n - \alpha_{max} m) = -1 </tex><br />
<br />
Так как <tex> \Phi_i = 2 n - \alpha_{max} m = O(n)</tex>, поэтому если <tex> f(n, m) = 1 </tex>, то средняя амортизационная стоимость модифицирующих операций составит <tex> a = O(1) </tex>.<br />
<br />
==Метод предоплаты==<br />
Представим, что использование определённого количества времени равносильно использованию определённого количества монет (плата за выполнение каждой операции). В методе предоплаты каждому типу операций присваивается своя учётная стоимость. Эта стоимость может быть больше фактической, в таком случае лишние монеты используются как резерв для выполнения других операций в будущем, а может быть меньше, тогда гарантируется, что текущего накопленного резерва достаточно для выполнения операции. Для доказательства оценки средней амортизационной стоимости <tex>O(f(n, m))</tex> нужно построить учётные стоимости так, что для каждой операции она будет составлять <tex>O(f(n, m))</tex>. Тогда для последовательности из <tex>n</tex> операций суммарно будет затрачено <tex>n \cdot O(f(n, m))</tex> монет, следовательно, средняя амортизационная стоимость операций будет <tex dpi = "150">a = \genfrac{}{}{}{}{\sum\limits^{n}_{i = 1} {t_i}}{n} = \genfrac{}{}{}{}{n \cdot O(f(n, m))}{n}</tex> <tex>= O(f(n, m))</tex>.<br />
<br />
====Примеры====<br />
=====Стек с multipop=====<br />
При выполнении операции <tex>\mathrm{push}{}</tex> будем использовать две монеты {{---}} одну для самой операции, а вторую {{---}} в качестве резерва. Тогда для операций <tex>\mathrm{pop}{}</tex> и <tex>\mathrm{multipop}{}</tex> учётную стоимость можно принять равной нулю и использовать для удаления элемента монету, оставшуюся после операции <tex>\mathrm{push}{}</tex>.<br />
<br />
Таким образом, для каждой операции требуется <tex>O(1)</tex> монет, значит, средняя амортизационная стоимость операций <tex>a = O(1)</tex>.<br />
<br />
==Источники информации==<br />
* [[wikipedia:Amortized_analysis | Wikipedia {{---}} Amortized analysis]]<br />
* Томас Кормен. Алгоритмы. Построение и анализ. - Санкт-Петербург, 2005. стр. 483-491.<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Амортизационный анализ]]</div>Arthurii