[quote=Ishka,28.07.2004, 15:02]sondern eine Klasse (im Prinzip eine Menge)[/quote]
ja, eine Menge von Funktion, deswegen schreibt man ja auch
Die Funktion f ist Element von O(N).

@eb: Du kannst dir mal folgendes Script anschauen:

http://fred.bioinf.uni-sb.de:4711/prog2_s....ion.pdf
http://fred.bioinf.uni-sb.de:4711/prog2_ss04/lectures/o-notation.pdf

lass dich aber nicht abschrecken... schau dir am besten die Beispiele und Graphen an\n\n

<!--EDIT|esskar|1091023273-->

OK, danke. Kann mir jetzt noch jemand ein Beispiel für folgende Komplexitäten geben:

1) O(logN)
2) O(N!)

n! ist exponentielles wachstum => NP-vollstaendige probleme, ...
log n => suche in einem binaeren baum

jo. wobei log der Logarithmus zur basis 2 ist

annahme, du hast eine array mit N elementen die sortiert sind ... sagen wir N sei 8, und jedes element kommt nur einmal vor
jetzt sollst du die Position eines Elementen bestimmen

ARRAY = [1, 2, 3, 4, 5, 6, 7, 8]; Du sollst nun das Element 7 finden... also splittest du das ARRAY in zwei hälften;

ARRAY1 = [1, 2, 3, 4]; ARRAY2 = [5, 6, 7, 8]
jetzt schaust du, ob dein Element im ersten oder im zweiten array liegt... man weiß ja, dass das array sortiert war, also musst du einfach z.b. 4 mit 7 und 5 mit 7 vergleichen...
du siehst, dass 4 das letzte element im linken, und somit das größte ist, deine 7 aber größer als 4 ist, und somit nicht im linken array sondern nur noch im rechten array sein kann; also nimmst du dir das rechte array vor und teilst wieder und vergleichst...
so kommst du dann in (maximal) O(log N) teilungen zum ergebnis\n\n

<!--EDIT|esskar|1091038156-->

die basis ist wurscht ;-P log(2, x) = log (b, x) / log (b, 2)
1/log (b, 2) ist ne konstante, und somit mit landau funktionenmengen nicht mehr interessant :-)

ist klar, anders aber schwerer zu zeigen

log 3 geht mit ner waage ganz gut.
log 4?

OK, so langsam wird das ganze etwas klarer. Ich habe noch ein paar Artikel gelesen, die ich über Google gefunden habe.
Nun noch ein paar weitere Fragen:

Was wird nun genau mit O() bezeichnet? N ist die Laufzeit. Und was ist dann O(N)? Würde es nicht reichen, wenn ich sage: Der Algorithmus hat die Komplexität von N? Man wüsste doch genau, was gemeint ist.

nein, N ist nicht die Laufzeit; N ist eine Menge

Ist gibt auch nicht nur O(N) vondern auch \Theta(N), o(N) (kleines o), \Omega(N), etcpp...

das Symbol vor (N) sagt, wie die Funktion wächst...

Wenn man sagt, dass ein Algorithmus in O(N) läuft, dann heißt das in Wirklichkeit:

Eine Funktion f, die den Algorithmus beschreibt, wächst nicht schneller als die Funktion g mit g(x) = x bzw. man kann schreiben

f ist Element von O(g) = f <= g

Wenn was in o(N) läuft, kann man sagen

f ist Element von o(g) = f < g; also f wächst langsamer als g

usw.

[E|B

,29.07.2004, 13:54]
Was wird nun genau mit O() bezeichnet? N ist die Laufzeit. Und was ist dann O(N)?

N ist nicht die laufzeit, sondern die menge/anzahl der elemente.
O(N) ist das laufzeitverhalten in abhängigkeit von N.
abe das habe ich weiter oben ja schon gesagt.

d.h. O(N^2) heisst: doppelte anzahl von eingabe-elementen = vierfache laufzeit
dreifache anzahl von eingabe-elementen: neunfache laufzeit