Wie berechnet man die Big-O-Komplexität des folgenden Algorithmus?

Question

Ich habe versucht, das Big-O des folgenden Algorithmus zu berechnen, und es stellt sich für mich als O (n ^ 5) heraus.Ich weiß nicht, was die richtige Antwort ist, aber die meisten meiner Kollegen bekommen 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;
        }
     }
}

Was ich getan habe, war von der innersten Schleife aus zu beginnen.Also habe ich berechnet, dass die innerste Schleife ausgeführt wird n/2 mal, dann bin ich zur zweiten verschachtelten for-Schleife gegangen, die ausgeführt wird i^2 zeiten und von der äußersten Schleife wird ausgeführt i zeiten als i variiert von 1 zu n.Dies würde bedeuten, dass die zweite verschachtelte for-Schleife insgesamt ausgeführt wird Sigma(i^2) from i=1 to i=n also insgesamt n*(n+1)*(2n+1)/6 Times.Der Gesamtbetrag, den der Code ausführen würde, lag also in der Reihenfolge von n^5 also kam ich zu dem Schluss, dass die Reihenfolge sein muss O(n^5).Stimmt etwas mit diesem Ansatz und der von mir berechneten Antwort nicht?

Ich habe gerade mit DSA angefangen und dies war meine erste Aufgabe, also entschuldige mich für alle grundlegenden Fehler, die ich gemacht haben könnte.

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;
        }
     }
}

Die dreifach verschachtelte Schleife entspricht der Summation $$\summe_{i=1}^{n}\summe_{j=1}^{i^2} \summe_{k=1}^{n/2} 1$$ $$=\frac{n}{2}(\summe_{i=1}^{n}\summe_{j=1}^{i^2}1)$$ $$=\frac{n}{2}(\summe_{i=1}^{n}i^2)$$ $$=\frac{n}{2} \cdot (\frac{1}{6}n(n+1)(2n+1))$$ $$= O(n ^4)$$

---

Hinsichtlich tatsächlich codeeffizienz, seit x=y+z ist in der Schleife invariant, extrahiert jeder gute optimierende Compiler die Anweisung aus der Schleife (in Compilersprache hissen Sie die Anweisung in den Schleifenvorheader), wodurch der kompilierte Code ausgeführt wird $ Aus(1)$.