O Notation Algorithmus

[gast23]

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²)?

[androphinx]

also keine Ahnung warum man das unbedingt so auseinander nehmen muss, aber wahrscheinlich wirst du das wohl gerade in der uni / schule haben. ich hab ehrlich gesagt nicht so wirklich viel ahnung von O-Notationen aber zumindest stimmt es rein rechnerisch...

Mfg androphinx

[gast23]

Ist für meine Arbeit und ich hab vergessen wie das alles genau war ;-D

[androphinx]

http://www.linux-related.de/index.html? ... tation.htm

http://de.wikipedia.org/wiki/Landau-Symbole

http://de.wikipedia.org/wiki/Sortierverfahren

Mfg androphinx

[solarix]

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

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".

In deinem Fall wird IMHO "O(n + n²)" also zu "O(n²)"....

hth..

[gast23]

Hm aber warum?

Wenn n=1millarde ist, dann fällt doch die eine foreach schleife mit sicherheit spürbar ins gewicht.

[franzf]

Naja...

Code: Alles auswählen

10^9 + 10^9*10^9 ~ 10^9 * 10^9

oder?
Selbst mit n=100 gilt schon

Code: Alles auswählen

100 + 100*100 = 10100 ~ 10000

Eine Abweichung von gerade mal 1%...
Kann evtl. kritisch sein bei manchen Anwendungen - aber im Allgemeinen eher nicht.

[gast23]

Gibt es evtl. noch eine andere Art die Laufzeit eines A. zu kommunizieren ohne Code?

[Panke]

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.