Komplexität

Renn25 · Anmeldungsdatum: 01.07.2005 Beiträge: 3

Hallo

Ich habe hier mal bei meiner angehängten Grafik ein Verständnisproblem bzw. scheiters da wohl an meinen Mathe-Kenntnissen.

Und zwar waren zu dem Diagramm folgenden zwei Sätze mit dazu die ich nicht verstehe.

-> Polynomiales Wachstum

beschränkt die Eingabegröße drastisch
-> Expotentielles Wachstum

noch sehr viel mehr

Heisst das in etwa soviel, da ich gegenüber den anderen Kennlinien z.B. log n weniger Eingabedaten habe, aber die Rechnenzeit trotzdem imens höher ist??? grübelnd

Wäre nett, wenn ihr mir da ma erklären könntet.

Danke
Renn

Crotaphytus · Anmeldungsdatum: 08.05.2005 Beiträge: 213

Ja, so ungefähr könnte man das ausdrücken. Diese Diagramme zeigen dir ja die Laufzeit abhängig von der Länge der Eingabe. Es ist denk ich klar, dass zum Beispiel ne Laufzeit, die irgendwie von n² abhängt, sehr viel schneller wächst als eine mit der Beziehung log n.

Was diese Aussagen wohl bedeuten sollen: Irgendwann wirst du bei jedem Programm an den Punkt kommen, an dem das Programm so lange läuft, dass die Laufzeit in keinem Verhältnis mehr zum eigentlichen Nutzen steht. Bei polynomialen (was n Wort...^^) oder vor allem exponentiellen Zusammenhängen ist das jetzt aber schon relativ früh erreicht (bei exponentiellem Wachstum kriegst du schon bei 50 Werten Laufzeiten, die man nur noch in Monaten angeben kann...), die Eingabegröße ist also stark beschränkt.

Renn25 · Anmeldungsdatum: 01.07.2005 Beiträge: 3

Danke dir!

Eine Frage habe ich noch. Und zwar. Gibt es irgendwie eine allgemeine Aussage, wie man für einen Algorithmus bestimmen kann, in welche Sparte dieser gehört. Also ob dieser z.B. O(n) oder O(log n) ist.

Es gibt zwar Beispielangaben, dass z.B. ein Suchalgorithmus O(log n) ist. Aber wenn man das nun nicht wissen würde. Kann man sich das irgendwie anders dann herleiten??

Danke
Renn

Crotaphytus · Anmeldungsdatum: 08.05.2005 Beiträge: 213

Das einzige, was du machen kannst, ist den Code anzuschauen und anhand dessen auf die Komplexität zu schließen. Wenn du zum Beispiel eine Schleife über alle Elemente der Eingabe drinhast ist die Komplexität schon mal mindestens O(n). Wenn dahinter noch ne Schleife kommt ist er immer noch O(n) (die Definition dieses O-Dingens da kennst du, oder?), wenn aber in der ersten noch ne zweite Schleife verschachtelt wäre kommst du bereits auf O(n²).

So musst du das Ganze halt anschauen und quasi "Operationen zählen". Kann unter Umständen relativ kompliziert werden, wenn verschachtelte Schleifen voneinander abhängen, wenn Schleifen komplizierte Abbruchbedingungen haben oder wenn du Rekursion drin hast...

Renn25 · Anmeldungsdatum: 01.07.2005 Beiträge: 3

thx

gruss
Renn