|
|
| (не показано 14 промежуточных версий 2 участников) |
| Строка 1: |
Строка 1: |
| − | == Операции ==
| + | #перенаправление [[Динамический массив]] |
| − | Определим операции, которые мы будем применять к саморасширяющемуся массиву:<br>
| |
| − | === get(i) ===
| |
| − | :Возвращает значение i-ой ячейки массива. Время выполнения — <tex>O(1)</tex>.
| |
| − | === set(i,x) ===
| |
| − | :В i-ую ячейку массива записывается элемент x. Время выполнения — <tex>O(1)</tex>.
| |
| − | === add(x) ===
| |
| − | :Добавление в массив элемента x. Время выполнения — <tex>O(1)</tex>; в худшем случае, при котором необходимо перенести все элементы из текущего массива в вдвое больший массив — <tex>O(n)</tex> (n — размер массива).
| |
| − | === size ===
| |
| − | :Возвращает количество элементов массива. Время выполнения — <tex>O(1)</tex>.
| |
| − | | |
| − | == Стоимость операции add(x) ==
| |
| − | === Метод предоплаты ===
| |
| − | [[Файл:Безымянный1.png|400px|thumb|right|Иллюстрация]] | |
| − | Применим амортизационный анализ (конкретно — метод предоплаты) для того, чтобы доказать, что среднее время работы операции add(x) — <tex>O(1)</tex>.<br>
| |
| − | Пусть у нас единицей стоимости операции является одна монетка. Тогда при каждой операции add(x), при которой нам не требуется копирование, мы будем использовать три монетки. Из них одна пойдёт на стоимость самой этой операции, а две будут в резерве (пусть, если мы добавили i-ый элемент, мы будем класть по одной монетке к элементам с номерами <tex>i</tex> и <tex>i-\frac{n}{2}</tex>). В итоге, к тому моменту, как массив будет заполнен, рядом с каждым элементом будет лежать по одной монетке, которую мы и можем использовать на его копирование в новый массив. Таким образом, амортизационная стоимость каждой операции add(x) — 3, и среднее время её работы — <tex>O(1)</tex>.
| |
| − | | |
| − | === Метод потенциалов ===
| |
| − | Метод потенциалов является обобщением метода предоплаты: здесь резерв не распределяется между отдельными элементами структуры данных, а является функцией состояния структуры данных в целом. Эта функция называется "потенциалом".
| |
| − | | |
| − | Общая схема метода потенциалов такова.
| |
| − | Пусть над структурой данных предстоит произвести n операций, и пусть <tex>\Phi_i</tex> — состояние структуры данных после i-й операции (в частности, <tex>\Phi_0</tex> — исходное состояние).
| |
| − | | |
| − | Потенциал представляет собой функцию из множества возможных состояний структуры данных во множество действительных чисел. Пусть <tex>t_i</tex> — реальная стоимость i-й операции.
| |
| − | | |
| − | Назовем амортизационной стоимостью i-й операции число:
| |
| − | | |
| − | <tex>a_i = t_i + \Phi_i - \Phi_{i-1},</tex>
| |
| − | | |
| − | т. е. сумму реальной стоимости операции плюс приращение потенциала в результате выполнения этой операции.
| |
| − | | |
| − | Теперь докажем с помощью метода потенциалов, что операция add(x) выполняется в среднем за <tex>O(1)</tex>.
| |
| − | За потенциал примем число:
| |
| − | <tex>\Phi(c, s) = 2s - c </tex>,
| |
| − | | |
| − | где с - размер массива, s - число элементов массива.
| |
| − | | |
| − | Рассмотрим два случая и посчитаем амортизационной стоимость операции add(x):
| |
| − | | |
| − | 1) Массив не расширяется: <tex> a_i = t_i + \Phi(c, s + 1) - \Phi(c, s) = 1+ (s + 1) - s = 2</tex>
| |
| − | | |
| − | 2) Массив расширяется: <tex> a_i = t_i + \Phi(2c, s + 1) - \Phi(c, s) = (s + 1) + 2 - s = 3 </tex>
| |
| − | | |
| − | В итоге, средняя стоимость операции add(x) — 3, а среднее время работы — <tex>O(1)</tex>.
| |
