Was ist die Komplexität von:Komplexität Berechnung
int f4(int n)
{
int i, j, k=1, count = 0;
for(i = 0; i < n; i++)
{
k *= 3;
for(j = k; j; j /= 2)
count++;
}
return count;
}
Ich weiß, es ist O (n^2), aber wie wird es berechnet? und warum ist es nicht n * log n?
Es gibt n äußere Schleifen. An jedem Punkt, k = 3i. Es gibt log2(k) inneren Schleifen (weil wir j bei jeder Iteration halbiert werden.)
log2(3i) = log3 (3i)/log3(2) = i/(constant)
So ist die Komplexität der inneren Schleife i ist. Mit anderen Worten, hat dieses Programm die gleiche Komplexität (aber nicht genau die gleiche Anzahl von Iterationen) als
int f4changed(int n)
{
int i, j, count = 0;
for(i = 0; i < n; i++)
{
for(j = 0; j < i; j++)
{
count++;
}
}
}
Dies ist O(n2)as you've already seen.
OK, vielen Dank! – yyy
Darf ich vorschlagen, '3 i' für die Stromversorgung zu schreiben, um mögliche Verwechslungen mit bitweiser xor zu vermeiden? –
Fertig, danke Hosam. –
i = 1 ergibt 3 Iterationen (der inneren Schleife) (3, 1, 0)
i = 2 ist, 8 (5 dann 3)
i = 3 ist, 13 (7 + 5 + 3)
Was Sie haben, ist eine Annäherung an eine arithmetic series, die O ist (n).
Zur Vollständigkeit (und um zu erklären, warum die genaue Anzahl der Iterationen keine Rolle spielt), beziehen Sie sich auf die Plain english explanation of Big O (das ist mehr für andere Leser als Sie, das Poster, da Sie zu wissen scheinen, was los ist).
Die Komplexität von Log (Pow (3, n)) ~ O (N). Wenn die innere Schleife k * = 2 wäre, wäre die Anzahl der Iterationen auch n gewesen.
Zur Berechnung von O (~) wird der höchste Leistungsbegriff verwendet und die anderen werden vernachlässigt. Log (Pow (3, n)) kann wie folgt begrenzt werden:
Log (Pow (2, n)) < = Log (Pow (3, n)) < = Log (Pow (4, n))
Jetzt Log (Pow (4, n)) = 2 * Log (Pow (2, n)).
Der höchste Leistungsbegriff hier ist n (wie 2 ist eine Konstante).
Nachdem du deine anderen Fragen angeschaut hast, scheint es, dass du nur versuchst, deine aktuelle Hausaufgabe zu erledigen ... Viel Glück damit :-) – scraimer
Ich suche nach Antworten auf einige HW-Fragen, die ich nicht bin Sicher, wie ich alleine löse, aber ich versuche nicht, alles von anderen erledigen zu lassen. Ich versuche nur zu verstehen, wie Komplexität funktioniert. – yyy
Corman Meisters Rivest und Stein. Das große weiße Buch. Fragen Sie nach dem Namen. –