0
Betrachten wir diese drei SchleifenGrundlegende Zeit Komplexität?
O (N^2)
int i = 0, s = 0;
while (2*i <= N*N) {
s+=i;
i++;
}
O (N)
int i = 0, s = 0;
while (s <= N*N) {
s+=i;
i++;
}
O (sqrt (N))
int i = 0, s=0, p=1;
while (s < N) {
i++;
p = p*i;
s += i;
}
Die Zeitkomplexität der ersten ist O (N^2), aber die zweite ist O (N) (mir scheint, dass N^2 geeigneter wäre). Woher? Zusätzlich, warum ist Schleife drei sqrt (N) und nicht log (N) - wie kann ich den Unterschied feststellen?
Dreieckszahlen. – EOF
Also dreieckige Zahl Iterationen bis N * N = O (N) und Dreieckszahl Iterationen bis N = O (sqrt (N)? – Aldo
) Muss ich * wirklich * dies buchstabieren? Betrachten Sie, wie die n-te Dreieckszahl wächst n erhöht – EOF