Analyse amortie

Question

Je suis tombé sur ce problème en étudiant ce qui demande de considérer une structure de données où une séquence de n opérations sont effectuées. Si la kième opération a un coût de k si c'est un carré parfait et un coût de 1 sinon, quel est le coût total des opérations et quel est le coût amorti de chaque opération. J'ai un peu de difficulté à trouver une formule de sommation qui donne la définition d'un carré parfait où je peux voir ce que la somme donne. Des pensées/conseils?

Answer 1

La somme de i^2 de 1 à n peut être calculée comme n(n+1)(2n+1)/6. Je l'ai trouvé dans un livre de mathématiques, ne peut pas trouver une formule simple en ligne. Mais vérifiez http://mathworld.wolfram.com/Sum.html, formule (6).

Pour calculer cette somme, soit n soit la racine carrée de k, arrondie à l'unité inférieure. La formule est proportionnelle à n^3 qui est sqrt(k)^3 = k^(3/2). Cela donne un temps amorti de O(k^(3/2)).