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

Question

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

Answer 1

Амортизированное время объясняется простыми словами:

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

Поэтому не имеет значения, если операция время от времени выполняется очень медленно, главное, чтобы «время от времени» было достаточно редко, чтобы медлительность можно было уменьшить.По сути, амортизированное время означает «среднее время, затрачиваемое на одну операцию, если вы выполняете много операций».Амортизированное время не обязательно должно быть постоянным;вы можете иметь линейное и логарифмическое амортизированное время или что-то еще.

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

Таким образом, каждое увеличение занимает примерно в два раза больше времени, чем при последнем увеличении.Но вы также ждали в два раза дольше, прежде чем сделать это!Таким образом, стоимость каждого расширения может быть «распределена» между вставками.Это означает, что в долгосрочной перспективе общее время, затраченное на добавление м элементы в массиве O(m), и, таким образом, амортизированное время (т.е.время на вставку) составляет O(1).

Answer 2

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

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

Или, говоря более строго,

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

Answer 3

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

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

Answer 4

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

Источник: https://en.wikipedia.org/wiki/Amortized_anaанализ#Dynamic_Array

«Динамический массив

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

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

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

Насколько я понимаю, это простая история:

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

Итак, вы идете прямо в конец/угол комнаты и начинаете складывать их.По мере того, как вы складываете их, в комнате постепенно заканчивается место.Однако по мере заполнения их было легко складывать.Получил деньги, положил деньги.Легкий.Это О(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-й размер комнаты = вмещает 2048 монет.
...
16-й размер комнаты = вмещает 65 536 денег.
...
32-й размер комнаты = вмещает 4 294 967 296 денег.
...
64-й размер комнаты = вмещает 18 446 744 073 709 551 616 денег.

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

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

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

Answer 5

Приведенные выше пояснения применимы к агрегатному анализу, идее получения «среднего значения» по нескольким операциям.Я не уверен, как они применимы к методу банкиров или методам амортизированного анализа физиков.

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

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

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

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

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

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

ИЛИ

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

1. Я знаю, что дорогостоящей операции будет предшествовать НЕСКОЛЬКО НЕЗАТРАТНЫХ операций.

2. Для анализа я собираюсь завысить стоимость некоторых малозатратных операций, ТАК, ЧТО ИХ АСИМПТОТИЧЕСКАЯ СТОИМОСТЬ НЕ МЕНЯЕТСЯ.

3. Благодаря этому увеличению недорогих операций я могу ДОКАЗАТЬ, ЧТО ДОРОГАЯ ЭКСПЛУАТАЦИЯ имеет МЕНЬШУЮ АСИМПТОТИЧЕСКУЮ СТОИМОСТЬ.

4. Таким образом, я улучшил/уменьшил АСИМПТОТИЧЕСКУЮ стоимость n операций.

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