Постоянное Амортизированное Время

Это означает, что со временем худший сценарий будет по умолчанию равен O(1) или постоянному времени. Общим примером является динамический массив. Если мы уже выделили память для новой записи, добавление будет O (1). Если мы не выделили его, мы сделаем это, выделив, скажем, вдвое больше текущей суммы. Эта конкретная вставка будет не быть O(1), а что-то другое.

важно то, что алгоритм гарантирует, что после последовательности операций дорогостоящие операции будут амортизированы и тем самым сделают всю операцию O(1).

или в более строгих терминах,

существует постоянная c, такая что для каждый последовательность операций (также один конец с дорогостоящей операцией) длина L, время не больше, чем c*L (спасибо Рафал Довгирдовские)

чтобы развить интуитивный способ мышления об этом, рассмотрим вставку элементов в динамический массив (например,std::vector в C++). Построим график, показывающий зависимость количества операций (Y), необходимых для вставки N элементов в массив:

вертикальные части Черного графика соответствуют перераспределению памяти для расширения массива. Здесь мы видим, что эта зависимость может быть грубо представлен в виде линии. И это линейное уравнение Y=C*N + b (C постоянно, b = 0 в нашем случае). Поэтому можно сказать, что нам нужно потратить C*N операции в среднем для добавления N элементов в массив, или C*1 операции по добавлению одного элемента (амортизированное постоянное время).

Я нашел ниже Википедии объяснение полезно, после повторного чтения в течение 3 раз:

Источник:https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array

"Динамический Массив

амортизированный анализ операции Push для динамического массива

рассмотрим динамический массив, который увеличивается в размерах по мере добавления к ней нескольких элементов например, ArrayList в Java. Если бы мы начали с динамического массива из размер 4, это займет постоянное время, чтобы подтолкнуть четыре элемента на него. Тем не менее, нажатие Пятого элемента на этот массив займет больше времени, поскольку массив должен был бы создать новый массив двойного текущего размера (8), скопируйте старые элементы в новый массив, а затем добавить новый элемент. Следующие три операции выталкивания будут аналогично принимать константу время, а затем последующее добавление потребует еще одного медленного удвоение размера массива.

В общем, если мы рассмотрим произвольное число нажатий n на массив размера n, мы замечаем, что операции push взять постоянное время, за исключением для последнего, который занимает O (n) времени для выполнения удвоения размера операция. Поскольку всего было n операций, мы можем взять среднее значение из этого и найти, что для выталкивания элементов на динамический массив принимает: O(n/n)=O (1), постоянное время."

в моем понимании, как простая история:

Предположим, у вас много денег. И, вы хотите, чтобы стек их в комнате. И, у вас есть длинные руки и ноги, столько, сколько вам нужно сейчас или в будущем. И, вы должны заполнить все в одной комнате, так что это легко заблокировать его.

Итак, вы идете прямо в конец / угол комнаты и начинаете складывать их. Как вы складываете их, медленно комната будет работать из пространства. Однако по мере заполнения их было легко складывать. Получил деньги, положил деньги. Простой. Это O(1). Нам не нужно перемещать какие-либо предыдущие деньги.

Как только номер заканчивается. Мы нужна другая комната, которая больше. Здесь есть проблема, так как у нас может быть только 1 комната, поэтому у нас может быть только 1 замок, нам нужно переместить все существующие деньги в этой комнате в новую большую комнату. Итак, переместите все деньги из маленькой комнаты в большую комнату. То есть, стек все из них снова. Итак, нам нужно переместить все предыдущие деньги. Итак, это O(N). (предполагая, что N-общее количество денег предыдущих денег)

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

предполагая, что N является большим, как 1 миллион даже в маленькой комнате, 2 операции по сравнению с N (1 миллион) на самом деле не является сопоставимым числом, поэтому он считается постоянным или O(1).

предполагая, когда мы делаем все выше в другой большой комнате, и снова нужно двигаться. Это все то же самое. скажем, N2 (скажем, 1 миллиард) - это новая сумма счета денег в большей комнате

Итак, у нас есть N2 (который включает N предыдущих, так как мы перемещаем все из маленькой комнаты в большую)

нам все еще нужно только 2 деятельности, одно вставка в более большую комнату, тогда другая деятельность движения для того чтобы двинуть к даже более большой комнате.

таким образом, даже для N2 (1 млрд), это 2 операции для каждого. что опять ничего не значит. Итак, она постоянна, или O (1)

Итак, как N увеличивается от N до N2, или другое, это не имеет большого значения. Он по-прежнему постоянен, или O(1) операций, необходимых для каждого из N .

---

теперь предположим, что у вас есть N как 1, очень мало, количество денег мало, и у вас есть очень маленькая комната, в которую поместится только 1 количество денег.

Как только вы заполняете деньги в комнате, комната заполняется.

когда вы идете в большую комнату, предположим, что он может поместиться только еще один деньги в нем, в общей сложности 2 количество денег. То есть, предыдущая перевела деньги и еще 1. И снова она наполняется.

таким образом, N растет медленно, и он больше не является постоянным O(1), так как мы перемещаем все деньги из предыдущей комнаты, но можем поместить только еще 1 Деньги.

после 100 раз, новый номер подходит 100 количество денег от предыдущих и еще 1 деньги, которые он может разместить. Это O (N), так как O(N+1) - O(N), то есть степень 100 или 101 одинакова, обе сотни, в отличие от предыдущей истории, те миллионы и миллиарды.

Итак, это неэффективный способ выделения комнат (или памяти/ ОЗУ) для наших денег (переменных).

---

Итак, хороший способ-выделить больше места, с полномочиями 2.

1-й размер комнаты = подходит 1 количество денег
2-й размер комнаты = подходит для 4 количество денег
3-й размер комнаты = подходит для 8 кол-во денег
4-й размер комнаты = подходит для 16 количество денег
5-й размер номера = подходит для 32 кол-во денег
6-я комната размер = подходит 64 кол-во денег
7-й размер комнаты = подходит 128 кол-во денег
8-й размер комнаты = подходит для 256 количество денег
9-й размер комнаты = подходит 512 количество денег
10-й размер комнаты= подходит 1024 кол-во денег
11-й размер комнаты= подходит 2,048 количество денег
...
16-й размер номера= подходит для 65,536 кол-во денег
...
32-й размер комнаты= подходит 4,294,967,296 количество денег
...
64-й размер комнаты= подходит 18,446,744,073,709,551,616 количество деньги

Почему это лучше? Потому что он выглядит медленно расти в начале, и быстрее позже, то есть по сравнению с объемом памяти в нашей оперативной памяти.

Это полезно, потому что в первом случае, хотя это хорошо, общая сумма работы, которая должна быть выполнена за деньги, фиксирована (2) и не сопоставима с размером комнаты (N), комната, которую мы взяли на начальных этапах, может быть слишком большой (1 миллион), что мы не можем использовать полностью в зависимости от того, можем ли мы получить столько денег, чтобы сэкономить вообще первый случай.

однако, в последнем случае, полномочия 2, он растет в пределах нашего ОЗУ. И поэтому, увеличивая мощности 2, Как Армотизированный анализ остается постоянным, так и он дружелюбен к ограниченной оперативной памяти, которую мы имеем на сегодняшний день.

приведенные выше объяснения применимы к агрегатному анализу, идее взятия "среднего" по нескольким операциям. Я не знаю, как они относятся к банкирам-методу или физикам-методам амортизированного анализа.

сейчас. Я не совсем уверен в правильном ответе. Но это было бы связано с принципиальным условием обоих физиков+методов банкира:

(сумма амортизированной стоимости операций) > = (сумма фактической стоимости операций).

главный трудность, с которой я сталкиваюсь, заключается в том, что, учитывая, что амортизированные асимптотические затраты на операции отличаются от нормальных асимптотических затрат, я не уверен, как оценить значимость амортизированных затрат.

то есть, когда кто-то дает мне амортизированную стоимость, я знаю, что это не то же самое, что и нормальная асимптотическая стоимость, какие выводы я должен сделать из амортизированной стоимости?

поскольку у нас есть случай, когда некоторые операции перегружены, а другие операции недозаряжены, одна гипотеза может быть, что цитирование амортизированных затрат по отдельным операциям было бы бессмысленным.

например: для кучи Фибоначчи цитирование амортизированной стоимости просто уменьшающегося ключа для O (1) бессмысленно, поскольку затраты уменьшаются "работой, выполненной более ранними операциями по увеличению потенциала кучи."

или

мы могли бы иметь другую гипотезу, что причины об амортизированных расходах следующим образом:

1. Я знаю, что дорогостоящая операция это будет предшествовать нескольким недорогим операциям.

2. для анализа я собираюсь завышать некоторые недорогие операции, так что их асимптотическая стоимость не меняется.

3. с этими увеличенными недорогими операциями я могу доказать, что дорогостоящая операция имеет меньшую асимптотическую стоимость.

4. таким образом, я улучшил / уменьшил асимптотическую границу стоимости n оперативный.

таким образом, анализ амортизированной стоимости + оценки амортизированной стоимости теперь применимы только к дорогостоящим операциям. Дешевые операции имеют ту же асимптотически-амортизированную стоимость, что и их нормальная асимптотическая стоимость.