нужно найти амортизированную стоимость последовательности, используя метод потенциальной функции

Question

Существует последовательность из n операций. I-я операция стоит 2i, если i - точная степень 2, стоит 3i, если i - точная степень 3, и 1 для всех других операций.

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

Я решил это с помощью агрегатного метода.Для которого я суммировал ряд степеней 2 и ряд степеней 3 и получил амортизированную стоимость 10. Затем я проверил это с помощью метода учета для действительно длинных последовательностей, и он не потерпел неудачу.Но моя проблема в том, как доказать, что он никогда не потерпит неудачу, я могу показать столько, сколько захочу, но это все равно не гарантирует, что через некоторое время он не потерпит неудачу.

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

Достаточно лишь нескольких идей о том, как доказать это в методе учета и как определить потенциальную функцию.Спасибо

Answer 1

Во-первых, забудьте о «1 для всех других операций» и «точной мощности 3» битов на минуту. Что, если стоимость составляла всего 2i, когда я являюсь точной степенью 2?

Хорошо, предположим, что мы делаем вид, что каждая операция стоит четыре. То есть для каждой операции мы помещаем четыре монеты в нашу «кучу долговых расписок» ... Затем мы используем эти монеты, чтобы «заплатить», когда мы достигаем фактических степеней 2. (Это один из способов описания метода потенциальной функции.)

Шаг 1: внесите четыре монеты. Нужно заплатить 2 * 1 = 2, поэтому наша куча монет на два.

Шаг 2: внесите еще четыре монеты. Нужно заплатить 2 * 2 = 4, поэтому наша куча снова в два.

Шаг 3: внесите четыре монеты. В куче теперь шесть монет.

Шаг 4: внесите четыре монеты. В куче теперь десять монет, но 4 - это степень 2, поэтому пришло время заплатить 4 * 2 = 8, поэтому наша куча снова падает до двух монет.

Шаги 5-7: внесите по четыре монеты каждая. Всего сейчас 14 монет.

Шаг 8: внесите четыре монеты (всего = 18), потратьте 8 * 2 = 16, еще раз две монеты останутся.

Довольно легко доказать, что устойчивое состояние здесь состоит в том, что мы продолжаем истощать наши монеты до постоянной (2), но никогда не опускаемся ниже. Поэтому амортизированная стоимость составляет четыре единицы за операцию.

Теперь предположим, что операция X стоит 2i, когда i - степень 2 (и ноль в противном случае). Предположим, что операция Y стоит 3i, когда i - степень 3 (и ноль в противном случае). И предположим, что операция Z стоит 1, за исключением случаев, когда i является степенью 2 или степенью 3. Обратите внимание, что ваша задача эквивалентна выполнению операции X и Y и Z для каждой итерации. .. Таким образом, если вы можете рассчитать амортизированную стоимость X, Y и Z отдельно, вы можете просто сложить их, чтобы получить общую амортизированную стоимость.

Я только что дал тебе X; Я оставляю Y и Z в качестве упражнения. (Хотя я не верю, что окончательный ответ - 10. Возможно, близко к 10) ...