Ulrike,
die Graphentheorie ist auf alle Fälle aufwendiger als die lineare Optimierung. In Kapitel 1 stehen ja vor allem Definitionen, die sich mir auch nicht gleich beim ersten Lesen erschlossen haben. Die wirklich klausurrelevanten Algorithmen kommen ab Kapitel 3. Beim Durcharbeiten dieser Algorithmen sind mir dann so allmählich die Definitionen aus Kapitel 1 klargeworden. Und lass Dich nicht entmutigen: Die Algorithmen/Übungsaufgaben wirken am Anfang total unverständlich und kompliziert (weil alles streng mathematisch formuliert ist und jedes dritte Zeichen irgenein griechischer Buchstabe ist...), aber wenn man sich einmal mit der Schreibweise "angefreundet" hat, dann stellen sich die meisten Aufgaben als gar nicht so schwierig heraus. Wenn Du konkrete Fragen hast, dann versuche ich Dir gern zu helfen!
Zu dem O(n): Dieses Zeichen ist ein Symbol für den Rechenaufwand. Es lässt sich daraus ablesen, wie stark der Rechenaufwand wächst, wenn die Problemgröße steigt. Ich probier's mal mit einem Beispiel: Stell Dir vor, Du hast einen gaaaaaaanz einfachen Algorithmus, der n Zahlen addiert und anschließend das Ergebnis speichert. Bei n=1 führt der Algorithmus keine Rechenoperation durch und eine Speicheroperation, also insgesamt eine Operation. Bei z.B. n=5 muss der Algorithmus vier Additionen und einen Speichervorgang durchführen, also fünf Operationen. Es sind also stets n Operationen durchzuführen, der Rechenaufwand des Algorithmus ist also O(n). Das bedeutet vor allem auch (und das ist bei Algorithmen mit großen Problemen wichtig!) dass bei doppelter Problemgröße der doppelte Rechenaufwand erforderlich ist.
Jetzt stellst Du Dir mal einen zweiten Algorithmus vor, der für jede Zahl n alle möglichen Binärzahlen mit n Stellen berechnet. Für n=1 gibt es genau zwei solche Binärzahlen, nämlich "0" und "1". Bei n= 2 werden es vier Binärzahlen ("00", "01", "10", "11"), bei n=3 acht, bei n=4 sechzehn usw...! Das heißt, immer wenn n um eins größer wird, dann wird sich auch der Rechenaufwand des Algorithmus verdoppeln --> der Rechenaufwand ist O(2 hoch n)!
Ich hoffe, das war einigermaßen verständlich...
Gruß Petra
