Фундаментальный вопрос амортизированного анализа

Структура данных поддерживает операцию foo, такую, что последовательность из n операций foo занимает Θ(n log n)время для выполнения в худшем случае.

а) Каково амортизированное время операции foo?

б) Насколько большим может быть фактическое время одной операции foo?

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

б) О(лог п)

Это верно? Как здесь правильно рассуждать?


big-o amortized-analysis
person Jeahinator    schedule 11.08.2019    source источник

Ответы (1)


arrow_upward
2
arrow_downward

а) если n операций занимает Θ(n log n), то по определению амортизированное время для foo операции равно Θ(log n) Амортизированное время усредняется по всем операциям, поэтому вы не учитываете наихудший случай только по отношению к операции, которая его вызвала, а амортизируется по отношению к все остальные тоже.

б) foo иногда может стоить O(n), но не более O(log n) раз. foo может даже иногда стоить O(n log n), если это не происходит чаще, чем постоянное (то есть, O(1)) количество раз.

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

Например, возьмем стратегию помещения элементов в вектор по одному, но увеличения памяти за счет удвоения выделенного размера каждый раз, когда новый элемент не помещается в текущее выделение. Каждый удвоенный экземпляр стоит O(n), потому что вам нужно копировать/перемещать все текущие элементы. Но амортизированное время на самом деле является линейным, потому что вы копируете 1 элемент один раз, 2 элемента один раз, 4 элемента один раз и т. д.: всего вы сделали log(n) удвоений, но сумма стоимости каждого из них составляет всего 1+2+4+8+...+n = 2*n-1 = O(n). Таким образом, амортизированное время этой реализации push составляет O(1), хотя в худшем случае это O(n).

person joanis    schedule 13.08.2019