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:
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?
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?