int z=1;
for（int i=0;i*i<n;i++）｛
z*=3;
for（int j=0;j<z;j++）{
// Some code
}
}
Antwort ist O (3^n). Ist es richtig? Wie kann man die Komplexität der verschachtelten Schleife herausfinden?Was ist das Big-O dieser verschachtelten Schleife?
äußere Schleife: i geht von 1 bis sqrt (n); innere Schleife: j, z geht bis zu 3^(sqrt (n));
"ein Code" ausgeführt werden soll 1 + 3 + 3^2 + ... +^3 (sqrt (n)) mal
let sum = 1 + 3 + 3^2 + ... + 3^(sqrt(n))
sum - 3*sum = 1 - 3(sqrt(n) + 1)
sum = 1 - 3(sqrt(n) + 1)/(1-3) = 2(3^(sqrt(n)+1) - 1)
2 (3^(sqrt (n) + 1) 1) < < O (3^sqrt (n))
O (3^sqrt (n)) ist genauer
Sie könnten das Problem mit Sigma-Notation auf diese Weise nähern -:
'3^sqrt (n)' ist die Ausführungszeit der letzten Iteration der äußeren Schleife, nicht die Gesamtausführung – mangusta
Sie sind herzlich eingeladen, eine genauere Antwort für die Summierung der Reihe i zur Verfügung gestellt. Es ist definitiv nicht O (3^n) jedoch. – softwarenewbie7331
nein, Ihre Komplexität ist die richtige, die Summe der geometrischen Progression ist 'b1 * (q^n-1)/(q-1), q = 3' was immer noch O ist (3^sqrt (n)), Entschuldigung für die Unannehmlichkeiten – mangusta