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

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

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

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

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

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

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

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

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

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

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

Чтобы разработать интуитивный образ мышления, рассмотрите возможность вставки элементов в динамический массив (например, 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), скопировать старые элементы в новый массив и затем добавить новый элемент. Следующие три операции 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 анализ Armotized остается постоянным, и он благоприятен для ограниченного объема оперативной памяти, имеющегося у нас на сегодняшний день.

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

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

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

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

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

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

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

ИЛИ

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

1. Я знаю, что дорогой операции предшествуют МНОГОКРАТНЫЕ операции с низкой стоимостью.

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

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

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

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

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

Итак, суть функции, которая выполняет функцию, Constant Amortized Timeсостоит в том, что это «среднее время» достигает предела, который не будет превышен, поскольку количество вызовов продолжает увеличиваться. Любой конкретный вызов может отличаться по производительности, но в долгосрочной перспективе это среднее время не будет расти все больше и больше.

Это существенная заслуга чего-то, что выполняет Constant Amortized Time.