Komplexitätsanalyse

[Jariel]

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:

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?

 

[Marco13]

Ich vote mal für "alles richtig"

 

[Jariel]

Die nächste Teilaufgabe wäre:

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)

 

[XHelp]

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

 

[Jariel]

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?

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]

Naja, ich würde generell die Variablen nicht vernachlässigen. Auch wenn die kleiner sind.

 

[Jariel]

Naja, ich würde generell die Variablen nicht vernachlässigen. Auch wenn die kleiner sind.

Hm ja, ich meinte jetzt die O-Notation wo man die kleineren Sachen vernachlässigt, also oben wäre dann O(n^2) richtig oder?

(Größenordnung von blub2 ist n).

 

[XHelp]

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]

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

 

[XHelp]

Deswegen heißen die Aufgaben meistens "... möglichst genau ..."