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

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

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

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

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