asymptotische Laufzeitkomplexität

[Janus]

Hallo, ich wollte nur mal zur Komplexität nachfragen ob ich das richtig verstanden habe oder nicht. Ihr sollt mir dann bitte JA sagen oder halt NEIN und die Gründe für mein Missverständnis.
Es geht um die asymptotische Laufzeitkomplexität bei Schleifen.

Bsp.:

for(i = 1..n){
for(j = 1..n){
//Aktion
}
}

Bei diesen 2 verschachtelten for Schleifen messe ich die Laufzeitkomplexität
indem ich mir nur die Eintritte in der inneren Schleife anschaue.
Bsp. n = 3
innere Eintritte = 9.....3²...O(n²)

anderes Bsp.:

for(i = 1..n){
for(j = 1..5){
//Aktion
}
}

die innere Schleife wird immer 5*n betretten.....Konstante fällt weg
..O(n)

anderes Bsp.:

for(i = 1..5){
for(j = 1..n){
//Aktion
}
}

Hier auch O(n) da die innere Schleife n*5 betretten wird.

mfg,
Janus

[ilute]

Bei solchen Schleifen ist die Frage einfach zu beantworten. Du zaehlst zunaechst einfach sturr die Anzahl der Operationen. Hier reicht die Anzahl der Iterationen ind er innersten Schleife. Die Anzahl der Operationen wird nun durch ein Polynom dargestellt. Bei for(1..n){ for(1..n){ ... } } etwa "a + bn + cn^2". Das nun die asymp. Laufzeit O(n^2) ist folgt aus der Tatsache, dass der Grad des Polynoms 2 ist (hatten wir ein Lemma fuer). Bei den anderen Schleifen von dir hat das resultierende Polynom einen niedrigeren Grad. Entsprechend erhaelst du eine andere Komplexitaet.

[Janus]

Hallo..also beim 1.Bsp. wäre somit das Polynom n² + n und da n² den größten Faktor hat .....O(n²)

Ich hätte da noch ein paar Fragen zu etwas schwierigeren Schleifen, nähmlich wenn sie von logarithmischer Komplexität sind.
Wir haben uns aufgeschrieben dass Schleifen oft von logarithmischer Komplexität sind wenn sich die Problemgröße in jedem Schleifenschritt verändert.(z.b. schönes Beispiel binäres Suchen)

Bsp.:
i = 1
while(i <= n){

j=n
while(j > 1){
j=j/10
}
i = i+1
}

Hier haben wir aufgeschrieben dass die Komplexität O(n*logn) ist.
Erkenne ich dieses logn nur an der Tatsache dass sich j immer durch 10 teilt...aber j ist doch nicht die Problemgröße...also kapier ich irgendwie nicht warum dieser Algorithmus von logarithmischer Komplexität ist.


Und noch was:
Bsp.:
for(int i = 1...n){
j = i
while(j <= i)
//Aktion
}
Hier beträgt die Komplexität O(n) oder?

mfg,
Hannes

[eViL_oNe]

zu 1: die innere Schleife wird genau lg n mal durchlaufen (lg = Logarithmus zur Basis 10), folglich ergibt sich eine Komplexität von O(n*log n )

zu 2: innere Schleife wird genau m mal durchlaufen => O(n), äußere Schleife wird genau n mal durchlaufen => O(n), d.h. O(n²)

[ilute]

Bei der zweiten Schleife entsteht fuer die Anzahl der Durchlaeufe der inneren Schleife eine Reihe nach dem Muster 1,2,3,...,n. Wie du weisst ist diese gleich n(n+1)/2, was ausgerechnet ein Polynom mit n^2 ergibt. Also ... O(n^2).

[Janus]

Hallo....irgendwie kapier ich das nicht....

i= 1
while(i <= n){
j=n
while(j > 1){
j=j/10
}
i = i+1
}

Wieso beträgt die Laufzeit für die innere Schleife O(logn)...wenn ich für n 4 hernehme kommt für log(n) = 0,60206 heraus.......obwohl ich die innere Schleife bei dem Beispiel 4mal betrette. Also wo ist da was gleich? Eigentlich müsste die Laufzeit für die innere Schleife O(n) lauten...

Beim 2ten Beispiel
Bsp.:
for(int i = 1...n){
j = i
while(j <= i)
//Aktion
}
}

n = 4
Die innere Schleife wird n mal betretten, genauso wie die aüßere Schleife.
Also ergibt sich ein Polynom: n+n. Genauso wie es mir von euch erklärt worden ist. Nicht n*n! Also O(n) meiner Meinung. Und wenn ich n(n+1)/2
einsetzt kommt für n = 4 10 heraus was nicht 4 ist......bitte um Aufklärung meiner Verwirrung.
mfg,
Janus

[TK1985]

Also beim 2. Beispiel würd ich auch sagen das die Komplexität O(n) ist. Die äußere Schleife wird ja n mal durchlaufen und jedes mal bevor die innere gestartet wird, wird j = i gesetzt und dann so lange durchlaufen bis j <= i ist. Da aber j = i zu Beginn ist, ist die Abbruchsbedingung gleich erfüllt oder eben nicht erfüllt. Höchstens in der inneren Schleife wird j noch irgendwie verändert, aber wenn nicht auf jeden Fall O(n)

MfG
Thomas

[eViL_oNe]

Hallo....irgendwie kapier ich das nicht....

i= 1
while(i <= n){
j=n
while(j > 1){
j=j/10
}
i = i+1
}

Wieso beträgt die Laufzeit für die innere Schleife O(logn)...wenn ich für n 4 hernehme kommt für log(n) = 0,60206 heraus.......obwohl ich die innere Schleife bei dem Beispiel 4mal betrette. Also wo ist da was gleich? Eigentlich müsste die Laufzeit für die innere Schleife O(n) lauten...


die äußere Schleife führt zum n-fachen Aufruf der inneren Schleife - die innere Schleife selber hat die Laufzeitkomplexität O(log n).
=> gesamte Laufzeitkomplexität: O(n*log n)

Beispiel:

Durchlauf mit n = 4:

innere Schleife wird jeweils log 4 = 0,60... mal ausgeführt. Davon nehmen wir das Supremum und kommen auf 1.

Durchlauf mit n = 100:

innere Schleife wird jeweils log 100 = 2 mal ausgeführt.


Die äußere Schleife bewirkt, dass wir die Ergebnisse jeweils mit n multiplizieren müssen, d.h.

Durchlauf mit n = 4:

innere Schleife wird insgesamt 4 mal ausgeführt, d.h. 4 * ceil(log(4))

Durchlauf mit n = 100:

innere Schleife wird insgesamt 200 mal ausgeführt, d.h. 100 * ceil(log(100))


das mit dem zweiten Beispiel habe ich total verpeilt und nicht bemerkt, dass die j niemals geändert wird :o

innere Schleife bricht niemals ab, da j IMMER kleiner gleich i ist - folglich hätten wir eine Endlosschleife - sicher, dass der Code so richtig ist?

[bloodriver]

deutsches wörterbuch ( oder auch deutscher duden genannt ) im internet mit suchfunktion

folgende begriffe:

asymptotische
Iterationen
Polynom
Lemma
Supremum

wann / wo / wie / wehalb / wieso / warum / weswegen / aus welchem grund / mit welchem ziel lernt und nutzt man solche wörter?

wäre nett wenn mir jmd nen link geben würde welcher sich auf bezieht ;)

[Janus]

Hallo...danke kapiers jetzt....
mfg,
Hannes

[Jan Krüger]

deutsches wörterbuch ( oder auch deutscher duden genannt ) im internet mit suchfunktion
Eigene Threads aufmachen ist schon verdammt kompliziert, gell?

[ilute]

@ blooddriver

ein mathematischer Duden ist das Nachschlagewerk deiner Wahl.

[eViL_oNe]

wann / wo / wie / wehalb / wieso / warum / weswegen / aus welchem grund / mit welchem ziel lernt und nutzt man solche wörter?


alles Stoff der 11 Klasse, Gymnasium :p

[Jan Krüger]

"Lemma" und "Supremum" hab ich an der Uni zum ersten Mal gehört.
In conclusio kann man durch scharfes Hinsehen o.B.d.A. trivialerweise sagen, dass hier offensichtlich eine monotone und nach oben beschränkte Diskussion läuft. Daraus folgt leicht, dass ich nicht weiter mitrede (Beweis: als Übung für den geneigten oder aufrechten Leser).

[Scavi]

wann / wo / wie / wehalb / wieso / warum / weswegen / aus welchem grund / mit welchem ziel lernt und nutzt man solche wörter?
..im zweitbesten Pisa-Bundesland (+ Freistaat) sollte man sowas eigentlich wissen :p