O Notation Algorithmus

Du bist neu in der Welt von C++? Dann schau hier herein!
Antworten
gast23
Beiträge: 103
Registriert: 11. August 2010 10:43

O Notation Algorithmus

Beitrag von gast23 »

Hi,

wenn ich z.B. ein Algorithmus habe der zwei geschachtelte foreach Schleifen nutzt für N Element ist die O Notation:

Bild

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
Beiträge: 170
Registriert: 26. Januar 2009 09:19
Wohnort: 127.0.0.2

Beitrag von 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
Beiträge: 103
Registriert: 11. August 2010 10:43

Beitrag von gast23 »

Ist für meine Arbeit und ich hab vergessen wie das alles genau war ;-D
solarix
Beiträge: 1133
Registriert: 7. Juni 2007 19:25

Beitrag von 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..:
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..
gast23
Beiträge: 103
Registriert: 11. August 2010 10:43

Beitrag von gast23 »

Hm aber warum?

Wenn n=1millarde ist, dann fällt doch die eine foreach schleife mit sicherheit spürbar ins gewicht.
franzf
Beiträge: 3114
Registriert: 31. Mai 2006 11:15

Beitrag von 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
Beiträge: 103
Registriert: 11. August 2010 10:43

Beitrag von gast23 »

Gibt es evtl. noch eine andere Art die Laufzeit eines A. zu kommunizieren ohne Code?
Panke
Beiträge: 10
Registriert: 29. Mai 2008 15:44

Beitrag von 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.
Antworten