Амортизированная сложность в условиях непрофессионала?

Ответ 1

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

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

Пример:
Поведение С++ std::vector<>. Когда push_back() увеличивает векторный размер выше своего предварительно заданного значения, он удваивает выделенную длину.

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

Однако, поскольку размер выделения был удвоен, следующие N-1 вызовы push_back() будут принимать время O(1) для выполнения. Таким образом, общее количество операций N будет по-прежнему принимать время O(N); тем самым давая push_back() амортизированную стоимость O(1) за операцию.

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

• Как и при неамортизированной сложности, нотация Big-O, используемая для амортизированной сложности, игнорирует фиксированные начальные накладные и постоянные коэффициенты производительности. Таким образом, для оценки эффективности амортизации с большими долями вы можете предположить, что любая последовательность амортизируемых операций будет "достаточно длинной", чтобы амортизировать фиксированные затраты на запуск. В частности, для примера std::vector<>, поэтому вам не нужно беспокоиться о том, действительно ли вы столкнетесь с дополнительными операциями N: асимптотический характер анализа уже предполагает, что вы это сделаете.

• Помимо произвольной длины, амортизационный анализ не делает предположений о последовательности операций, стоимость которых вы измеряете, - это наихудшая гарантия на любую возможную последовательность операций. Независимо от того, насколько сильно операции выбраны (скажем, злонамеренным противником!), Амортизированный анализ должен гарантировать, что достаточно длительная последовательность операций не может стоить последовательно больше, чем сумма их амортизируемых затрат. Вот почему (если специально не указано как квалификатор), "вероятность" и "средний случай" не имеют отношения к амортизированному анализу - не более, чем к обычному большому анализу большого О-вывода!

Ответ 2

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

(от Cormen и др., "Введение в алгоритмы" )

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

Предположим, что вы работаете в лотерее. (Не покупая лотерейный билет, с которым мы мгновенно займемся, но работаем с самой лотереей.) Вы печатаете 100 000 билетов, которые вы будете продавать по 1 валюте каждый. Один из этих билетов предоставит покупателю 40 000 единиц валюты.

Теперь, предполагая, что вы можете продать все билеты, вы сможете заработать 60 000 единиц валюты: 100 000 единиц валюты в продажах, минус 40 000 единиц денежной единицы. Для вас стоимость каждого билета составляет 0,60 единиц валюты, амортизированная по всем билетам. Это надежная ценность; вы можете банка на нем. Если вам надоело продавать билеты самостоятельно, а кто-то приходит и предлагает продать их по 0,30 единиц валюты каждый, вы точно знаете, где вы стоите.

Для лотерейного покупателя ситуация другая. Покупатель имеет ожидаемую потерю 0,60 единиц валюты при покупке лотерейного билета. Но это вероятностно: покупатель может покупать десять лотерейных билетов каждый день в течение 30 лет (чуть более 100 000 билетов) без выигрыша. Или они могут спонтанно купить один билет в один прекрасный день и выиграть 39999 единиц валюты.

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

Часто указывалось, что амортизированный анализ применяется к ситуации, когда операция с высокой стоимостью является редкой, и это часто случается. Но не всегда. Рассмотрим, например, так называемую "очередь банкиров", которая является очередью "первым в первом" (FIFO), состоящей из двух стеков. (Это классическая функциональная структура данных, вы можете создавать дешевые стеки LIFO из неизменяемых односвязных узлов, но дешевые FIFO не так очевидны). Операции выполняются следующим образом:

put(x):  Push x on the right-hand stack.
y=get(): If the left-hand stack is empty:
           Pop each element off the right-hand stack and
             push it onto the left-hand stack. This effectively
             reverses the right-hand stack onto the left-hand stack.
         Pop and return the top element of the left-hand stack.

Теперь я утверждаю, что амортизированная стоимость put и get равна O(1), предполагая, что я начинаю и заканчиваю пустую очередь. Анализ прост: я всегда put в стек правой руки и get из стека левой руки. Поэтому, помимо предложения If, каждый put является push, и каждый get является pop, оба из которых являются O(1). Я не знаю, сколько раз я буду выполнять предложение If - это зависит от шаблона put и get - но я знаю, что каждый элемент перемещается ровно один раз из правого стека в левый стек. Таким образом, общая стоимость по всей последовательности n put и n get равна: n push es, n pop s и n move s, где a move является pop на a push: другими словами, 2n put и get приводят к 2n push es и 2n pop s. Таким образом, амортизированная стоимость одного put (или get) равна единице push и одному pop.

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

1) Получить и удалить самый старый элемент очереди,

2) Поместите новый элемент в очередь,

3) Найдите значение текущего максимального элемента.

Ответ 3

Принцип "амортизированной сложности" состоит в том, что, хотя что-то может быть довольно сложным, когда вы это делаете, поскольку это не делается очень часто, оно считается "не сложным". Например, если вы создаете двоичное дерево, которое время от времени требует балансировки - скажите один раз каждые 2^n вставки - потому что, хотя балансировка дерева довольно сложна, это происходит только один раз в каждых n вставках (например, один раз при вводе номера 256, затем снова на 512, 1024 и т.д.). На всех других вставках сложность O (1) - да, она принимает O (n) один раз каждые n вставок, но это только вероятность 1/n, поэтому мы умножаем O (n) на 1/n и получаем O (1). Таким образом, это называется "Амортизированная сложность O (1)", поскольку, поскольку вы добавляете больше элементов, время, затрачиваемое на перебалансирование дерева, минимально.

Ответ 4

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

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

Ответ 5

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

Ответ 6

Скажите, что вы пытаетесь найти k-й наименьший элемент несортированного массива. Сортировка массива будет O (n logn). Итак, нахождение k-го наименьшего числа - это просто определение индекса, поэтому O (1).

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

Если мы выполним n запросов на поиск k-го наименьшего значения, он все равно будет O (n logn), потому что он доминирует над O (1). Если мы усредним время каждой операции, это будет:

(n logn)/n или O (logn). Итак, сложность времени/количество операций.

Это амортизированная сложность.

Я думаю, что так оно и есть, я просто изучаю это.