O Notation Algorithmus
O Notation Algorithmus
Hi,
wenn ich z.B. ein Algorithmus habe der zwei geschachtelte foreach Schleifen nutzt für N Element ist die O Notation:
Wenn ein Algorithmus 1. eine Foreach über N Element und danach als neue Anweisung dann 2. eine geschachtelte foreach Schleife besitzt
=> ist dann die Notation O(n + n²)?
wenn ich z.B. ein Algorithmus habe der zwei geschachtelte foreach Schleifen nutzt für N Element ist die O Notation:
Wenn ein Algorithmus 1. eine Foreach über N Element und danach als neue Anweisung dann 2. eine geschachtelte foreach Schleife besitzt
=> ist dann die Notation O(n + n²)?
-
- Beiträge: 170
- Registriert: 26. Januar 2009 09:19
- Wohnort: 127.0.0.2
-
- Beiträge: 170
- Registriert: 26. Januar 2009 09:19
- Wohnort: 127.0.0.2
ich meinte mich zu erinnern, dass man nur die dominanten Ausdrücke angibt (wenn n gegen unendlich geht..).
Ach ja.. in androphinx' Link stehts ja..:
hth..
Ach ja.. in androphinx' Link stehts ja..:
In deinem Fall wird IMHO "O(n + n²)" also zu "O(n²)"....http://www.linux-related.de/index.html?/coding/o-notation.htm hat geschrieben: Salopp ausgedrückt: "strebt die Anzahl der Eingabewerte n gegen unendlich, so wird der n2-Term dominant und alle anderen Terme sind zu vernachlässigen".
hth..
Naja...
oder?
Selbst mit n=100 gilt schon
Eine Abweichung von gerade mal 1%...
Kann evtl. kritisch sein bei manchen Anwendungen - aber im Allgemeinen eher nicht.
Code: Alles auswählen
10^9 + 10^9*10^9 ~ 10^9 * 10^9
Selbst mit n=100 gilt schon
Code: Alles auswählen
100 + 100*100 = 10100 ~ 10000
Kann evtl. kritisch sein bei manchen Anwendungen - aber im Allgemeinen eher nicht.
Die O-Notation ist eben gerade nicht dafür da, die Laufzeit eines
Algorithmus exakt anzugeben. Sie teilt eher die Alogrithmen in
Klassen ein, in denen alle Algorithmen ungefähr gleich gut sind -- im jeweils schlechtesten Fall.
Man kann natürlich auch den durchschnittlichen oder den besten Fall betrachten. Im Grunde ist es immer interessant, die tatsächlich auftretenen Eingaben zu betrachten und konkret zu messen.
Algorithmus exakt anzugeben. Sie teilt eher die Alogrithmen in
Klassen ein, in denen alle Algorithmen ungefähr gleich gut sind -- im jeweils schlechtesten Fall.
Man kann natürlich auch den durchschnittlichen oder den besten Fall betrachten. Im Grunde ist es immer interessant, die tatsächlich auftretenen Eingaben zu betrachten und konkret zu messen.