Hallo,
wir haben letztens die O-Notation behandelt zur Beschreibung des Aufwands von Algorithmen. Wir haben aber nur Forschleifen beschrieben, also wenn ich 2 Forschleifen für das eine Feld habe, dann haben wir das mit n^2 (Oder ist es O(n^2)?) beschrieben.
Was kann man aber noch alles „beschreiben“ beim Algorithmus? Im I-Net bin ich über so etwas nicht fündig geworden, nur was die O-Notation ist und wer sie erfunden hat.
Wäre für jede Anregung dankbar!
Hallo!
Wie du ja schon erwähnt hast, kann durch die O-Notation der Aufwand (also Rechenzeit, Speicherverbrauch…) eines Algorithmus in Abhängigkeit der Eingabe dargestellt werden. Das ist bei einer einzelnen For-Schleife eben O(n) bzw. bei geschachtelten O(n^2), wenn in beiden Schleifen n Durchläufe sind.
Prinzipiell kann damit jeder Algorithmus dargestellt werden. Dazu siehst du dir einfach an, welcher Teil wie oft ausgeführt wird und wie lange so ein Teil braucht. Das multiplizierst du dann entsprechend und addierst die Teilkomplexitäten. Zum Schluss suchst du eine obere Schranke entsprechend der Definition der O-Notation.
Wolltest du Informationen in dieser Richtung oder eher etwas anderes?
Nico
Kleine Ergänzung:
Man nimmt dann den Exponenten des größten Gliedes.
Also wenn die Komplexität durch f(n)=5x³-7x²+8x+1 beschreiben werden kann ist die O Notation einfach O(n)=n³
Hallo,danke erst ein mal für deine Antwort!
Prinzipiell kann damit jeder Algorithmus dargestellt werden.
Dazu siehst du dir einfach an, welcher Teil wie oft ausgeführt
wird und wie lange so ein Teil braucht. Das multiplizierst du
dann entsprechend und addierst die Teilkomplexitäten. Zum
Schluss suchst du eine obere Schranke entsprechend der
Definition der O-Notation.
Was meinst du mit obere Schranke?
Also wir haben uns folgende aufgeschrieben:
O(1)
O(log n)
O(n)
O(n*log n)
O(n^2)
O(n^k)
O(2^n)
Unter diesen Sachen kann ich mir nichts vor stellen außer O(1) und O(n)… gibt es nicht irgendwo Beispiele? Nutzt man die O-Notation überhaupt in der Praxis?
Also deine Antwort hilft mir schon ein bisschen weiter. Wie sieht das denn mit If-Bedingungen aus? Werte ich da nur den Inhalt des Rumpfes oder auch die „Bedingung“ selbst aus?
Hallo,
vielleicht kann dir der Link hier etwas helfen http://www.linux-related.de/index.html?/coding/o-not…
Da findest Du auch etwas zu Schleifen beispielsweise.
Gruss
Petra
Moin, Keozor,
weißt Du denn, wofür das O steht?
Gruß Ralf