Rechenaufwand von Algorithmen

sönke,

die letzte Frage zuerst: nun ja, in der ea wird es auch gefragt, und zwar als einzige abweichung zur Klausur 03/09, welche ansonsten identisch ist mit unserer ea.
vielleicht ein hinweis darauf, dass man es grob verstanden haben sollte 🙂

ansonsten ist es weniger dramatisch als es aussieht:
es geht um eine grobe schätzung, wie groß der aufwand für wirklich große anzahl von daten n (z.b. knoten) ist.
sinn des ganzen: auswahl der richtigen algorithmen um ein abrauchen des computers zu vermeiden oder das unserer köpfe...so in der art 😛

wenn z.b. ein "echter" maximaler rechenaufwand (anzahl der maximal durchzuführenden operationen) (n-1)*(n-1) vorliegt, werden für eine grobe schätzung die einsen ignoriert (weil es für wirklich große n nicht viel ausmacht) und der ganze term "zusammengeschmolzen" und somit dann als schätzung (!) O(n²) angegeben.

wenn du z.b. O(n²) als angabe der rechenaufwandsschätzung hast, besagt das folgendes: anzahl der knoten verdoppeln hat ein vervierfachen des rechenaufwands zur folge. anzahl der knoten verdreifachen hat ein verneunfachen des rechenaufwands zur folge. schau dir das mal anhand es aufwands von (n-1)(n-1) an (für den O(n²) heißt) und prüfe mit n=500, n=1000 und n=1500, was rauskommt.

O(n) z.b. heißt, dass der aufwand ca. um das doppelte steigt, wenn du n verdoppelst, also sich "analog" zu n verändert.
O(log n) heißt, dass der aufwand um einen konstanten betrag wächst, wenn sich n verdoppelt.
O(1) heißt, dass der rechenaufwand beschränkt ist und über einen konstanten wert nicht hinausgeht wenn du z.b. n verdoppelst.
O(wurzel(n)) heißt bspw., dass f nur auf ca das doppelte wächst, wenn n vervierfacht wird. oder: f wächst um wurzel(2) wenn n verdoppelt wird. z.b. für n=500 und n=1000 schon gut zu erkennen.
(diese angaben hab ich aus dem internet)

es ist einfach auf einen blick schneller zu erkennen, wie aufwändig ein algorithmus ist bzw wieviel mehraufwand eine veränderung in n bedeutet. bei der "echten" angabe (n-1)*(n-1)+n ist man einen moment länger am grübeln als bei der schätzung O(n²).

ergo: wichtig im hinterkopf zu behalten - es ist eine schätzung und sie ist für richtig große n gedacht.

die ersten beiden angaben in beispiel 2.1 verstehe ich übrigens auch nicht...
aber in der dritten zeile siehst du wieder einen akt des "zusammenschmelzens" 😎

ok. hoffe, es ist einigermaßen klar geworden. bin selbst erstaunt, wieviel text wieder zusammengekommen ist

Vielen Dank für die Antwort! Ich konnte jetzt die Aufgaben nachvollziehen.
Mich hatten einfach die Beispiele völlig verwirrt. "Es gilt O(n)=O(n^2) aber nicht O(n^2)=O(n)"

Also für mich besteht das Studium an der Fernuni zu mindestens 50% daraus die Skripte in verständliche Formulierungen zu übersetzen. 40% sind dann noch auswendig lernen und verstehen ist der Rest.