# Komplexitätsanalyse



## Jariel (2. Dez 2010)

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 (2. Dez 2010)

Ich vote mal für "alles richtig"


----------



## Jariel (2. Dez 2010)

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 (2. Dez 2010)

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


----------



## Jariel (2. Dez 2010)

XHelp hat gesagt.:


> 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 (2. Dez 2010)

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


----------



## Jariel (2. Dez 2010)

XHelp hat gesagt.:


> 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 (2. Dez 2010)

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 (3. Dez 2010)

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


----------



## XHelp (3. Dez 2010)

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


----------

