Амортизированный анализ

Question

Я столкнулся с этой проблемой при изучении, которая просит рассмотреть структуру данных, где выполняется последовательность из n операций. Если k-я операция имеет стоимость k, если это идеальный квадрат, а стоимость 1 в противном случае, какова общая стоимость операций и какова амортизированная стоимость каждой операции.

У меня возникли некоторые трудности с предложением формулы суммирования, которая дает определение идеального квадрата, где я могу видеть, что дает сумма. Есть мысли / советы?

Answer 1

Сумма i^2 от 1 до n может быть рассчитана как n(n+1)(2n+1)/6, Я нашел это в математической книге, не могу найти простую формулу онлайн. Но посмотрите http://mathworld.wolfram.com/Sum.html, формула (6).

Для расчета этой суммы пусть n быть квадратным корнем kокруглено вниз. Формула пропорциональна n^3 который sqrt(k)^3 = k^(3/2), Это дает амортизированное время O(k^(3/2)),