амортизированный анализ на двоичную кучу

Question

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

Итак, последовательность, в которой мы выполнили n операций extract_min и изначально содержали n элементов. Означает ли это, что вся последовательность будет обработана за время O (n), поскольку каждая операция равна O (1)?

Answer 1

Давайте сначала разберемся с этим: удаление ВСЕХ элементов в куче с помощью extract_min операций занимает O (N log N) время.

Это факт, поэтому, когда вы спрашиваете: «Постоянное амортизированное время extract_min подразумевает линейное время для удаления всех элементов?», Вы действительно спрашиваете: «Может ли extract_min принимать постоянное амортизированное время, даже если это занимает O (N log N) время извлечь все элементы? "

Ответ на этот вопрос зависит от того, какие операции поддерживает куча.

Если куча поддерживает только операции add и extract_min, то каждый extract_min, который не выходит из строя (в постоянном времени), должен соответствовать предыдущему add. Затем мы можем сказать, что add принимает амортизированное O (log N) время, а extract_min принимает амортизированное O (1) время, поскольку мы можем назначить все его не- постоянные затраты к предыдущему add.

Если куча поддерживает операции O (N) time make_heap (амортизированные или нет), то можно выполнять операции N extract_min, ничего не делая остальное, которое добавляет до O (N log N) времени. Тогда вся стоимость O (N log N) должна быть отнесена к операциям N extract_min, и мы могли бы не утверждать, что extract_min занимает амортизированное постоянное время.