20 сент. 2011 г., 06:20 от Rohit chauhan

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

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

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

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

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

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

Ответы на вопрос (0)

20 сент. 2011 г., 14:00 от 56.9k

забудьте о «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)

ВАШ ОТВЕТ НА ВОПРОС