Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Aufwände…
Hi,
wär vllt. jemand so nett und erklärt n bisschen was zur Aufwandsberechnung?
Ich versteh z.b. die ganzen Definitionen und kann auch die rechenregeln nachvollziehn,allerdings wenn ich dann konkret Code vor mir hab,tu ich mich ziemlich schwer da den Aufwand anzugeben…
Wie geht ihr da am besten vor?Irgendeine bestimmte Systematik?
Vllt. mag das auch wer so n bisschen anhand der Klausur vom 23. März 2004 erklären.(Aufgabe 1 + 2)
(http://www9.informatik.uni-erlangen.de/Teaching/WS2005/AlgoI/Material/klausur.2004Mae23.pdf)
wäre echt dankbar,das ist so eines der wenigen Dinge die mir noch unklar sind.Kommt aber in obiger Klausur z.b. 2mal vor…
Gruß
Daniel
Hallo,
Hab mir auch eine kleine Einsteigerhilfe gesucht… ist zwar nicht wirklich sehr tiefgreifend, aber für einen Anfgang ganz gut!
http://www.linux-related.de/index.html?/coding/o-notation.htm
Viel Spaß…
das sieht schonmal gut aus ,vielen dank…
Viel hilfreiches zu dem Thema findest du auch in “Introductions to Algorithms”. hat mir zumindest recht gut zu verstehen gegeben wie das mit den Aufwänden so ist.
Einfache Grundregeln
Vielleicht hilfs auch, sich ein paar Faustregeln zu merken, wenns um Code geht:
Komplexitäten von sequenziellen Anweisungen werden einfach addiert. Wenn eine Schleife aussenrum ist, wird die Summe mit Zahl der Schleifendurchläufe multipliziert.
Laufzeiten geschachtelter Schleifen werden auch multipliziert.
Bei Produkten fallen Konstanten weg. Bei Summen zählt nur der höchste Exponent, also ist jedes Polynom vom Grad n auch in O(x^n).
Mal 2 Beispiele:
f o r ( i n t i = 1 ; i<=k ; i ++) foo ( n ) ;
foo(n) hat Aufwand O(log n).
Somit ergibt sich also als aufwand:
k*O(log n) und k als Konstante fällt also weg…also bleibt O(log n)
f o r ( i n t j = 1 ; j<=n ; j ++) b a r ( j ) ;
bar(j) habe O(n)
Da bar(j) ja von der Laufvariable j abhängt ergäbe sich als Aufwand…
O(1) + O(2) + …+O(n-1)+O(n)
also quasi O(n+n-1…+1)
die folge n+n-1+n-2+…+1 ist ja laut Gauß n*(n+1)/2 also (n^2+n)/2
laut den Faustregeln ist dann alles also O(n^2).
Hab ich das so richtig durchdacht?
Sollte so sein, ja.
Beim 2 Beispiel muss man nicht einmal so kompliziert denken. Deine For Schleife lauft n mal. Deine funktion hat den aufwand O(n). Daraus sieht man bereits ohne Rechnung das der Gesamtaufwand O(n*n) ist.
Du hast leider nicht richtig gedacht, weil der Aufwand von
O(n + n-1 + n-2 + … + 2 + 1) = O(max(n, n-1, n-2, …, 2, 1)) = O(n)
Siehe hierzu auch Folien, Kapitel 13, Folie 30ff.
O(n^2) wird aber in der Musterlösung angegeben…allerdings is mir dein Einwand auch plausibel…
confused
Kann’s sein, dass diese Formel nur für eine konstante Anzahl von Summanden (also nicht n wie hier) gilt?
Und… O(\sum_{i=1}^n i) = O(n(n+1)/2) = O(n^2), also hätten wir am Schluss dastehen O(n) = O(n^2)
f o r ( i n t j = 1 ; j<=n ; j ++) b a r ( j ) ;
bar(j) habe O(n)Ich glaube, du hast dann nicht n mal n…1 als Laufzeit, sondern n mal n.
Da steht zwar bar(j), aber die Komplexität soll O(n) sein. z.b. könnte bar(j) das Element j in einer Reihung suchen → Laufzeit n, weil n Einträge in der Reihung. Da ist die Frage, wie man die Angabe interpretiert 
immer so, dass es am einfachsten ist. Zudem ist O() immer eine Grenzwertaussage, und egal wie viel man reinsteckt, wird die Laufzeit, auch wenns sie zeitlich gesehen kürzer ist, immer zur selben Klasse gehören.
Damit erklärt sich die Musterlösung recht einfach. n mal n = n^2.
Vermutlich kann man bei bei den Komplexitätsaufgaben immer gut diskutieren, solange man etwas begründen kann, weil O(n^x) ∈ O(n^y) ∀ x ≤ y.
Nochmal einige Beispiele (g) :
(foo mit O(log n), bar mit O(n) ,k sei eine Konstante,n eine Variable,i und j Laufvariablen)
1)for ( int i = 1 ; i <= n ; i ++) {
fo o ( i ) ;
}
bar (n ) ;
Für die Schleife: n*O(log n) also n * log n
Dann ergibt sich also:
O(nlog n) + O(n) = O(max (nlog n),(n))=O (n* log n)
for ( int i = 1 ; i <= k ; i ++) {
fo o (n ) ;
bar (n ) ;
}
in der For schleife:
O(log n )+O(n)=O(max(log n),n)=O(n);
Schleife wird k-mal durchlaufen
also k*O(n)…k als Konstante fällt weg ,somit -->O(n)
3)for ( int i = 1 ; i <= n ; i ++) {
bar ( i ) ;
for ( int j = 1 ; j <= k ; j++) {
fo o (n ) ;
}
}
innerste Schleife:k*O(log n) -->O(log n)
zusammen mit bar O(log n)+O(n) =O(max(n),(log n))=O(n)
Schleife wird n mal durchlaufen…n ist aber wohl hier keine Variable mehr.
Somit n*O(n)—>O(n^2)?
for ( int i = 1 ; i <= n ; i ++) {
for ( int j = 1 ; j <= i ; j++) {
bar ( fo o ( j ) ) ;
}
}
Jau,in diesem Beispiel fahren sie schweres Geschütz auf 
innerste Schleife:
bar(foo(j)) ich würde hier folgende Regel heranziehn:
O(O(f(n))=O(f(n));
somit wäre: bar(foo(j)) = O(O(log n))=O(log n)
100% sicher bin ich mir aber nicht.
nach erste Schleife i durchläufe…
also iO(log n)…so ,wie wert ich jetz i? Als konstante oder variable?
Ich würde i mal als konstante sehn…also bleibts log n.
nach der äußeren Schleife gilt dann O(nlog n)…
Allerdings bin ich mir hier absolut nicht sicher…
Meinungen sind wie immer erwünscht…
1-3 würd ich auch so lösen…
- wir wissen nicht, in welcher Größenordnung der return-Wert von foo liegt (0? 1? n?). Da er aber als Parameter für bar verwendet wird ist das nicht ganz unbedeutend. Aber gehen wir mal von n aus. Dann haben wir also für bar(foo(j)) O(n + log n) = O(n).
Innere Schleife: j zählt von 1 bis zur Laufvariable i der äußeren Schleife. i ist im Mittel 1/2 n, also ist j im Mittel 1/4 n. 1/2 und 1/4 sind konstante Faktoren, fliegen also raus. Damit ergibt sich für die innere Schleife ein Aufwand von O(nn). DerGesamtaufwand beträgt also O(nn*n) = O(n^3).
Das ist vielleicht ein wenig schlampig formuliert, aber das beste was mir dazu einfällt. Ich hoffe man darf so argumentieren.
Edit: zu meim Beitrag oben: Ja, irgendiwe müsste O(n^2) rauskommen. Wahrscheinlich kann man diese Formel wirklich nur bei konstanten Summandenzahl verwenden.
@Comrade:
letztes Beispiel:
bar(foo(j))
ist doch auch
y=foo(j)
bar(y)
demnach
O(log n) + O(n) => O(n)
mit äußerer Schleife (1*, 2* … n*)
O(n^2)*O(n)=O(n^3)
Stimmt das jetzt? Ich bin mir nicht wirklich sicher.
Edit: Da war wohl jemand schneller … aber so habe ich es ja auch
@Nico: Ich glaube nicht, dass mans in der vierten so machen kann. Ich hab zwar keine Ahnung, was rauskommt, aber wenn du y = foo(j) setzt und dann bar(y) berechnest, ist ja y bzw. bar nicht mehr von j abhängig.
Man muesste wohl folgende Summe loesen, um das Ergebnis zu erhalten:
Summe i=1…n (Summe j=1…i (j * log j) )
Falls jemand weiss, was Summe j=1…i (j * log j) ist, koennte mans glaub ich so berechnen.
Also ich erklär mir das bar(foo(j)) jetzt so…im worst case ist eben ,wie liwo sagte,j=n…also der max wert.(weil i-max=n und j-max =i)
die methode bar ruft also foo auf und holt den Rückgabewert…dafür brauchts den Aufwand für foo…jetz kommt noch der aufwand von bar dazu also wie liwo schrieb O(n)+O(log n)=O(n).
die innere Schleife wird im “worst-case” n-mal durchlaufen,im mittel n/4.das 1/4 ist also egal.die äußere n-mal bzw im mittel n/2 mal,das 1/2 ist zu vernachlässigen,somit insgesamt O(n^3)…
Für mich ist es so plausibel…
Naja, ich glaub nach wie vor nicht, dass es so geht. Ich denk aber auch, dass so was kompliziertes in der Klausur nicht drankommt.
Das mit dem O(n) + O(log n) stimmt glaub ich nicht, weil im “worst case” hat man für foo den Aufwand log n, und für bar den Aufwand O(n). Das n in O(n) ist aber proportional zu log n, also O(n log n). Also ich weiß nicht, ob das stimmt,was ich hier schreibe, aber z.B. wenn man ein Verfahren hat, das O(log n) hat, und das dann n mal durchführt (denn man kann ja bar einfach durch n-faches Durchführen von foo ersetzen, glaub ich), muesste man O(n log n) haben.
Ich weiß auch nicht ob man das einfach so mit “worst case” sagen kann, es ist ja eigentlich kein "worst case " im sinne eines Algorithmus, sondern die j-Schleife wird ja nicht nur einmal n-mal durchlaufen, sondern auch noch einmal (n-1) mal, einmal (n-2) mal, … etc. Deshalb denke ich auch an die Summe, die man berechnen müsste.
Also auch nochmal zur vierten, ich seh das a bissl anders.
zunächst mal wird der Aufruf von bar(foo(j)) genau nΣi (wobei die Summe von i=1 bis n läuft) also ausgerechnet hat man n0.5n(n+1) durchläufe. So jetzt weis man schon mal wie oft man O(logn) malgenommen werden muss. Nun hat man aber noch das Problem das man beim besten willen nicht weis was denn foo(j) eigentlich zurückliefert es könnte ja z.B. wieder j liefern oder j^2 oder j^1000 oder was weis ich was. Um das ganz nun aufzudröseln ging ich wie folgt vor:
bisher: O(0.5(n^2(n+1))(O(foo(j)) + O(logn))) so dann hab ich wie ihr angenommen das foo(n) im worst case das maximale liefert und ersetze das für foo(j). nun wähle ich eine Funktion aus der Menge O(foo(n)) aus z.B. 0.5foo(n) (das kann man so machen, Algorithmenbuch nachlesen!) und ersetze die als Repräsentant für die Funktionsklasse O(foo(n)). Dann noch das ganze vereinfachen so bekomm ich letztlich:
O(n^3*max(foo(n),logn))
(ohne Gewähr)
- Wir haben nie bewiesen das diese Formel gilt. (nur mit zwei Argumenten)
- Bei dem Beispiel hat man wohl eher O(0.5n(n+1)) = O(n^2).
P.S. Musterlösungen zu den Klausuren gibts irgendwie nicht oder?
muss mich korrigieren obige Lösung stimmte nicht ganz