Comment calcualte le Big-O de la complexité de l'algorithme suivant?

Question

J'ai essayé de calculer le Big-O de l'algorithme suivant et il est sorti à O(n^5) pour moi.Je ne sais pas quelle était la bonne réponse est, mais la plupart de mes collègues sont prise en O(n^3).

for(i=1;i<=n;i++)
{
    for(j=1 ; j <= i*i ; j++)
    {
        for(k=1 ; k<= n/2 ; k++) 
        {
        x = y + z;
        }
     }
}

Ce que j'ai fait a été de commencer à partir de la boucle de plus bas niveau.Donc j'ai calculé que le plus intime de la boucle sera exécuté n/2 fois, puis je suis allé à la deuxième instruction de boucle for qui va exécuter i^2 fois et en allant de l'extérieur de la boucle sera exécuté i fois i varie de 1 pour n.Cela signifierait que la deuxième instruction de boucle sera exécuté un total de Sigma(i^2) from i=1 to i=n donc un total de n*(n+1)*(2n+1)/6 fois.De sorte que le montant total que le code à exécuter est venu à être dans l'ordre de n^5 j'en ai donc conclu que la commande doit être O(n^5).Est-il quelque chose de mal avec cette approche et de la réponse que j'ai calculé?

Je viens de commencer avec DSA et c'était ma première mission afin excuses pour les erreurs de base que j'ai fait.

Answer 1

for(i=1;i<=n;i++)
{
    for(j=1 ; j <= i*i ; j++)
    {
        for(k=1 ; k<= n/2 ; k++) 
        {
        x = y + z;
        }
     }
}

Le triple-boucle imbriquée est équivalent à la somme $$\sum_{i=1}^{n}\sum_{j=1}^{i^2} \sum_{k=1}^{n/2} 1$$ $$=\frac{n}{2}(\sum_{i=1}^{n}\sum_{j=1}^{i^2}1)$$ $$=\frac{n}{2}(\sum_{i=1}^{n}i^2)$$ $$=\frac{n}{2} \cdot (\frac{1}{6}n(n+1)(2n+1))$$ $$=O(n^4)$$

---

En termes de réel efficacité du code, depuis x=y+z est invariant dans la boucle, tout bon compilateur optimisant extrait de la déclaration de la boucle (dans le compilateur parler, à se hisser à la déclaration de la boucle preheader), ce qui rend le code compilé exécuter dans $O(1)$.