Массив с увеличением/уменьшением размера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Условие)
Строка 21: Строка 21:
  
 
==Амортизационная стоимость каждой операции==
 
==Амортизационная стоимость каждой операции==
Пусть наш массив расширяется в 2 раза, и уменьшается в 2 раза, когда длина массива в 4 раза больше кол-ва элементов в массиве. В этом случае амортизационная стоимость каждой операции будет 3. Докажем это используя метод предоплаты:
+
Пусть наш массив расширяется в 2 раза, и уменьшается в 2 раза, когда длина массива в 4 раза больше кол-ва элементов в массиве. В этом случае амортизационная стоимость каждой операции будет O(1). Докажем это используя метод предоплаты:
  
 
===Расширение массива===
 
===Расширение массива===

Версия 06:46, 30 марта 2011

Определение:
Массив - структура данных,набор однотипных переменных доступ к которым осуществляется по индексу.


Для массива с увеличением/уменьшением размера возможно выполнение следующих операций:

  • Add(x) - добавление элемента в конец массива
  • Set(i,x)- присвоение i-му элементу значение х
  • Get(i) - значение i-го элемента
  • Del - удаление элемента

Операции с массивом

Add

Добавляет в конец массива элемент X. Если размер массива превышен, то выполняется операция расширения массива. Время выполнения операции в худшем случае O(n)

Set

В i-ую ячейку массива, записывается значение X. Время выполнения O(1)

Get

Возвращает значение i-ой ячйеки массива. Время выполнения O(1)

Del

Удаляет последний элемент массива. В случае если кол-во элементов в массиве в С раз меньше его длины то происходит сжатие в B раз. (С,B-константы, зависящие от метода реализации массива) Время выполнения операции в худшем случае O(n)

Амортизационная стоимость каждой операции

Пусть наш массив расширяется в 2 раза, и уменьшается в 2 раза, когда длина массива в 4 раза больше кол-ва элементов в массиве. В этом случае амортизационная стоимость каждой операции будет O(1). Докажем это используя метод предоплаты:

Расширение массива

При каждом добавлении элемента одну монетку будем тратить на добавление самого элемента, будем класть по 1 монетке на ячейку в которую добавили, и по 1 монетке на ячейку стоящую на n/2 позиции раньше текущей. В этом случае при каждом расширении гарантируется что на каждой ячейке имеется хотя бы одна монета.

Сужение массива

В случае с удаление ячейки будем действовать по схожей стратегии. 1 монетку на удаление, 1 монетку на элемент стоящий на позиции i-n/4, и 1 монетку на текущий элемент (точнее на его могилку после удаления). При это даже в самом худшем случае (только что расширились а потом n/4 раза удалили) у нас будет хватать денег на сужение.