Ich versuche, die Zeit Komplexität dieses Pseudo-Code gegebenen Algorithmus, um herauszufinden:Zeitkomplexität eines Algorithmus (Nested Loops)
sum = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= n/6; j++)
sum = sum + 1;
Ich weiß, dass die erste Zeile läuft
n-mal
Aber ich bin mir nicht sicher über die zweite Zeile.
Hier haben Sie einen einfachen Doppel-Loop:
for i=1;i<=n;i++
for j=1; j<=n/6; j++
so, wenn Sie zählen, wie oft der Körper der Schleife wird ausgeführt (dh wie oft diese Zeile Code sum = sum + 1; wird ausgeführt), Sie sehen es:
n * n/6 = n²/6
, die in Bezug auf die big-O-Notation ist:
O (n²)
weil wir nicht wirklich für den konstanten Term, denn wie n wächst, macht der konstante Term keinen (großen) Unterschied, wenn es da ist oder nicht!
Wann und nur, wenn Sie voll und ganz verstehen, was ich sage, können Sie mit dieser netten Frage tiefer gehen: Big O, how do you calculate/approximate it?
jedoch beachten Sie bitte, dass solche Fragen für die mehr geeignet sind Theoretical Computer Science, anstatt SO.
Sie machen n * n/6 Operationen, daher ist die Zeitkomplexität O (n^2/6) = O (n^2).
Genauer gesagt, 'n * (n/6)' Operationen: Die Komplexität ist die gleiche, aber das Ergebnis ist unterschiedlich. – chqrlie
Sigma-Notation verwenden, können wir die asymptotischen Grenzen Ihres Algorithmus finden Sie wie folgt vor:
Zeitkomplexität = Summe? :) (n * n/6) –
Wäre das nicht nur O (n^2)? Scheint einfach zu sein. – Aede
Es muss nicht immer schwer sein :) –