Изменения

'''Амортизационный анализ''' {{- --}} метод подсчета времени, требуемого для выполнения последовательности операций над структурой данных. При этом время усредняется по всем выполняемым операциям , и анализируется средняя производительность операций в наихудшем худшем случае.}}Такой анализ чаще всего используется, чтобы показать, что даже если некоторые из операций последовательности являются дорогостоящими, то при усреднении по всем операциям средняя их стоимость будет небольшой за счёт низкой частоты встречаемости. Подчеркнём, что оценка, даваемая амортизационным анализом, не является вероятностной: это оценка среднего времени выполнения операций для худшего случая. {{Определение | definition ='''Средняя амортизационная стоимость операций''' {{---}} величина <tex>a</tex>, находящаяся по формуле: <tex dpi = "150">a = \frac{\sum\limits^{n}_{i=1} {t_i}}{n}</tex>, где <tex>t_1,t_2, ... t_n</tex> - время выполнения операций <tex>1,2, ... , n,</tex> совершённых над структурой данных.

==1. Метод средних усреднения (метод группового анализа). 2. Метод потенциалов. 3. Метод предоплаты (метод бухгалтерского учета). ==Метод усреднения== В методе усреднения амортизационная стоимость операций определяется напрямую по формуле, указанной выше: суммарная стоимость всех операций алгоритма делится на их количество. ====Пример====Рассмотрим стек с операцией <tex>multipop(a)</tex> {{---}} извлечение из стека <tex>a</tex> элементов. В худшем случае она работает за <tex>O(n)</tex> времени, если удаляются все элементы массива. Однако прежде чем удалить элемент, его нужно добавить в стек. Итак, если в стеке было не более <tex>n</tex> элементов, то в худшем случае с каждым из них могли быть произведены 2 операции - добавление в стек и извлечение из него. Например, если было <tex>n</tex> операций <tex>push</tex> - добавление в стек, стоимость каждой <tex>O(1)</tex>, и одна операция <tex>multipop(n)</tex>, то суммарное время всех операций - <tex>O(2n)</tex>, всего операций <tex>n+1</tex>, а значит, амортизационная стоимость операции - <tex>O(1)</tex>.

Определим Пусть <tex>t_1,t_2, ... t_nn</tex> {{--- время выполнения }} количество операций , <tex>1,2, ... , n.m</tex><br>В методе средних амортизированная стоимость операций определяется следующим образом: суммарная стоимость всех операций алгоритма делится на их количество, т.е. <tex>\frac{\sum^{n---}_{i=1} {t_i}}{n}</tex>. При этом каждой операции присвается одна и та же средняя амортизированная стоимостьразмер стека.Тогда:

Рассмотрим стек с операцией <texdpi = "150">multipop(a)</tex> - извлечение из стека <tex>a</tex> элементов. В худшем случае она работает за <tex>O(= \frac{\sum\limits^{n}_{i=1} {t_i}}{n} = \frac{\sum\limits^{n}_{i=1} \sum\limits^{m}_{j=1} {t_{ij}}}{n} = \frac{\sum\limits^{m}_{j=1} \sum\limits^{n)</tex> времени, если удаляются все элементы массива. Однако прежде чем удалить элемент, его нужно добавить в стек. Итак, если в стеке было не более <tex>}_{i=1} {t_{ij}}}{n</tex> элементов}, то в худшем случае с каждым из них могли быть произведены 2 операции - добавление в стек и извлечение из него. Например, если было <tex>n</tex> операций где <tex>push{t_{ij}}</tex> {{--- добавление в стек, стоимость каждой }} время выполнения <tex>O(1)i</tex>, и одна операция -ой операции над <tex>multipop(n)j</tex>, то суммарное время всех операций - ым элементом. Величина <tex>O(2n)</tex>, всего операций <tex>\sum\limits^{n+}_{i=1} {t_{ij}}</tex>не превосходит 2, а значитт. к. над элементом можно совершить только 2 операции, амортизационная стоимость операции время выполнения которых равно 1 {{--- <tex>O(1)</tex>}} добавление и удаление.Тогда:

<tex>a \leq \frac{2m}{n} \leq 2,</tex> так как <tex>m \leq n</tex>. Таким образом, cредняя амортизационная стоимость операций <tex>a = O(1)</tex>. ==Метод потенциалов== ==Метод предоплаты (метод бухгалтерского учета)==