Komplexitätsanalyse

Jariel

Mitglied
Ich hab folgendes "programm" mit den 2 Methoden blub1 und blub2. Dabei hat blub 1 eine Größenordnung von O(log(n)) und blub2 hat die Größenordnung O(n). n ist eine Eingabevariable vom Typ int. Nun soll ich die beste Komplexität für folgenden Fall in O-Notation angeben:

Java:
for (int i = 1; i <= n; i++) {
blub1(i);
}
blub2(n);

Möchte gerne eine Bestätigung bzw. Korrektur für meine Rechnung:

Die Schleife läuft n mal durch, also wird blub1 n mal ausgeführt d.h. => n * log(n)
blub2 wird einmal ausgeführt => n * log(n) + n

Bei der Angabe in O-Notation wird nur die Größenordnung angegeben, d.h. das + n fällt weg da es sozusagen nur marginal Einfluss auf die Größe hat, also bleibt in O-Notation übrig: O(n*log(n))

Stimmt das?
 

Jariel

Mitglied
Die nächste Teilaufgabe wäre:

Java:
for (int i = 1; i <= k; i++) {
blub1(n);
blub2(n);
}

wobei k eine positive Konstante ist.

Nun wäre die Größe k * log(n) + k * n

da n > log(n) fällt k * log(n) weg.

Was passiert jetzt mit der Konstanten k?
Kommt die in die O-Notation mit rein => O(k * n)
oder nicht => O(n)
 

Jariel

Mitglied
Konstanten können vernachlässigt werden. Das wird aus der Definition von den Landau-Symbolen deutlich.

Hm und wenn das so verschachtelt ist auch vernachlässigen?

Java:
for (int i = 1; i <= n; i++) {
blub2(i);
for (int j = 1; j <= k; j++) {
blub1(n);
}
}

Weil blub2 > blub1 und k eine Konstante nimmt man also die Größenordnung von blub2 * n und vergisst das blub1 , oder?
 

XHelp

Top Contributor
O ist die größere Schranke, d.h. auch wenn du dich etwas nach oben hin verschätz hast, ist es ja erstmal nicht schlimm.
Aber n^2 sieht plausiebel aus.
 

Marco13

Top Contributor
Genaugenommen (oder eben auch ungenaugenommen) könnte man ja immer sagen: Die Funktion ist in O(BusyBeaver(Ackermann(n)^Graham)^Graham) :D
 

Neue Themen


Oben