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

There is a sequence of n operations, The ith operation costs 2i if i is an exact power of 2, costs 3i if i is an exact power of 3, and 1 for all other operations.

Hi first up I want to say that it is a homework problem and I don't want you to solve it for me.

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

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

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


algorithm amortized-analysis
person ocwirk    schedule 20.09.2011    source источник

Ответы (1)


arrow_upward
8
arrow_downward

Во-первых, забудьте на минуту о битах «1 для всех остальных операций» и «точная степень 3». Что, если бы стоимость была всего 2i, когда i — точная степень числа 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...)

person Nemo    schedule 20.09.2011