qtforum.de

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

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

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

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

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

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

Mfg androphinx

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

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

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

hth..

Hm aber warum?

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

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.

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

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.