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

Question

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

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

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

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

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

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

В общем случае, если мы рассмотрим произвольное число нажатий 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-ой размер комнаты = подходит для подсчета денег
3-й размер комнаты = подходит на счет 8 денег
4-й размер комнаты = подходит для 16 денег
5-й размер комнаты = подходит для 32 денег
6-й размер комнаты = подходит для 64 денег
7-й размер комнаты = подходит для 128 денег
8-й размер комнаты = подходит для подсчета денег
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 анализ Armotized остается постоянным, и он благоприятен для ограниченного объема оперативной памяти, имеющегося у нас на сегодняшний день.

Answer 5

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

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

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

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

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

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

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

ИЛИ

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

1. Я знаю, что дорогой операции будет предшествовать НЕСКОЛЬКО операций НИЗКОЙ СТОИМОСТИ.

2. Ради анализа я собираюсь переоценить некоторые недорогие операции, ТАК, ЧТО ИХ АСИМПТОТИЧЕСКАЯ СТОИМОСТЬ НЕ ИЗМЕНЯЕТСЯ.

3. С этими увеличенными низкозатратными операциями я могу доказать, что ДОРОГАЯ РАБОТА имеет МАЛЕНЬКУЮ АСИМПТОТИЧЕСКУЮ СТОИМОСТЬ.

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

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