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

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)).