Laufzeitsanalyse und Komplexitätsklasse

b1zarRe · 29. Aug 2011

Hi,

ich habe Probleme bei folgenden 2 Aufgaben:
http://www8.pic-upload.de/29.08.11/h885xqe7ffzb.jpg

Was ich herausgefunden habe:

1.Aufgabe:
Äußere Schleife wird durchlaufen mit den Werten 0,1,2,...,n-1 Also: n-1+1 Durchläufe = n Durchläufe!
Innere Schleife durchläuft für ein i mithilfe j die Werte: 0,1,2,...,i-1 also i Durchläufe

Also insgesamt n*i Durchläufe... ich glaube auch das immer i < n gelten muss... also würde ich auf O(n) schätzen? Was sagt ihr dazu?

2.Aufgabe:
Äußere Schleife wird durchlaufen mit den Werten i, i/2, (i/2)/2, .... Wieviele Durchläufe sind das?- Wie kann man das umschreiben... vllt log(i) Durchläufe!?!

Innere Schleife durchläuft die Werte 0,1,2,....,i-2,i-1 Also: i-1+1 Durchläufe = i Durchläufe.

Wäre nett, wenn ihr mir da weiterhlefen könntet...

SlaterB · 29. Aug 2011

1.
i ist doch von n abhängig, wieso läßt du das bei der Komplexität weg wie eine Konstante?

bei beiden Aufgaben:
du sitzt doch anscheinend zu Hause herum und hast alle Zeit der Welt, programmiere das doch und zähle exakt die Werte,
wie oft die äußeren und inneren Schleifen durchlaufen werden und zwar für verschiedene n, 5, 10, 50, 100, 500 usw.,
wenn dir dann nicht selber auffällt ob das log oder was anderes ist, dann helfen vielleicht anderen diese Infos

b1zarRe · 29. Aug 2011

Also wäre bei 1. die Komplexität O(i * n) ? :/

Ansonsten: Leider kann ich in der Klausur nicht einfach nachprogrammieren, und würde das gerne verstehen... :/

SlaterB · 30. Aug 2011

die Komplexität kann nur irgendwas mit n sein, solange du nicht alle Handvoll gebräuchlichen nennen kannst,
muss man kaum was machen

'in der Klausur kann ich nicht' ist immer ein sinnloses Argument, denn dann dürftest du hier auch nicht fragen, oder kannst du das während der Klausur?
du bist noch nicht in der Klausur, und darfst jetzt noch Hilfsmittel zum Lernen verwenden, z.B. im Internet schauen,
oder wie von mir vorgeschlagen dieses Programm untersuchen, das soll dir genau zum benötigten Verständis helfen,
sicher wäre es besser ohne, aber das kannst du eben noch nicht, also musst du dorthin kommen,
mit deinem Kopf, wenn dir jemand anders irgendwas erzählt ist das auch nicht zielführender

Illuvatar · 30. Aug 2011

O(i*n) macht doch keinen Sinn. Die Komplexität kann ja nicht von i abhängen.
Überleg dir einfach nur: Jemand sagt dir eine Zahl n, wie oft wird die (innerste) Schleife dann durchlaufen? (Überleg dir erstmal paar Beispiele. Die Anzahl Durchläufe kann natürlich nur von n abhängen!)

Wenn du das hast, dann kannst du im zweiten Schritt überlegen was das für eine Komplexitätsklasse ist.

b1zarRe · 30. Aug 2011

Ich habe es nochmal probiert: http://www8.pic-upload.de/30.08.11/og7gkw97mzw7.jpg

Zur Erläuterung: Ich habe die beiden Schleifen für n = 3, n = 4, n = 5, n = 6 getestet. Ich habe mir dann, wie man auf dem Bild sieht, immer den aktuellen Wert von i bzw j ausgeben lassen. Herauskam:

Für n = 3: Äußere Schleife wird genau 3(also n mal) durchlaufen und die innere auch n mal(also 3 * j vorzufinden). Wäre in dem Fall n * n also O(n^2)
Für n = 4: Äußere wird n mal durchlaufen innere hingegen n+2; also: n * n+2 -> O(n^2)
Für n = 5: Äußere: n, Innere: n+5; also n * n+5 -> O(n^2)
Für n = 6: Äußere:n, Innere: n+9; Also n*n+9 -> O(n^2)

Insgesamt kann man also auf O(n^2) abschätzen. Ist das vorgehen SO richtig? ODER muss ich die Werte zusammenaddieren und daraus ableiten, was das für ein Aufwand ist? (man sieht häufig eine SUmmenformel bei diesem Thema)... also sprich:

n = 3: Summe von i Werte = n. Summe von j Werten = n-2
n = 4: Summe i Werte = n+2. Summe von j Werten = n-2
n = 5: Summe von i Werten = n+5 Summe von j Werten = n-2
n = 6: Summe von i Werten = n+9 Summe von j Werten = n-2

Also überall (ohne Konstanten) n*n -> O(n²) ?
Welche Vorgehensweise ist korrekt???

SlaterB · 30. Aug 2011

wenn n gerade mal 3, 4, 5 ist, dann kannst du Faktoren wie +2, +5, +9 nicht als Konstanten weglassen
generell sind kleine Zahlen für sich nicht gut genug,
wie ich geschrieben hatte besser auch für n = 50 und 100 testen, die Ausgaben anschauen reicht dann nicht mehr, int-Variablen hochzählen

wie du aus einem n und nochmal n+9 zusammen n*n+9 statt 2*n + 9 folgerst ist mir nicht ganz klar,
n*n als Endergebnis hast du aber korrekt, ja

relativ deutlich wäre das, wenn bei n=100 nämlich irgendwas um n*n =10.000 rauskommt,
falls es nur die Hälfte, 5000, wäre, dann könnte man gut testen ob bei n=200 auch die Hälfte von 40.000 herauskommt,
1/2 * n^2 wäre ja auch noch n^2

wie könnte man es normal erkennen? so wie du es wohl auch in etwa erklärst,
äußere Schleife bis n, innere mehr oder weniger auch -> n^2

Illuvatar · 30. Aug 2011

Ich bin grade in Erklärlaune:

Die Ausgaben der Werte von "i" sind für die Berechnung relativ irrelevant. Die Komplexität soll ja angeben, wie oft der Code ausgeführt wird, der dann an der Stelle steht, wo du jetzt den Wert von "j" ausgibst.
Wenn man sich das Bild von dir so anschaut, dann sieht man:
- n=3: 3 Durchläufe (1 + 2)
- n=4: 6 Durchläufe (1 + 2 + 3)
- n=5: 10 Durchläufe (1 + 2 + 3 + 4)
Jetzt erkennt man das Muster - und da kommen dann diese Summenformeln ins Spiel. Die Anzahl Durchläufe sind nämlich (1 + 2 + ... + (n-1)), bzw

$eq.latex$

Und daran kannst du jetzt wieder sehen, dass das hier O(n^2) hat.

b1zarRe · 30. Aug 2011

@SlaterB
auf n*n + 9 komme ich deshalb, weil die äußere Schleife n mal durchlaufen wird und die innere(in dem Beispiel für den Wert: 6) n + 9. Da die beiden verschachtelt sind und nicht etwa nacheinander folgt: n * n + 9 = n^2 + 9 = O(n^2). Wären die beiden Schleifen nacheinander, dann wäre es 2n + 9, richtig.

@Illuvatar
Also ist bei der Aufwandsanalyse so gesehen (bei 2 geschachtelten Schleifen, oder 3) die Anzahl der Durchläufe der innersten Schleife wichtig? bzw.:

Deine Summenformel ist ja so aufgebaut das das Summenzeichen Sigma den Start i = 0 bis n -1 angibt(also die äußere Schleife) und bei jedem Mal wird die i's addiert. Was insgesamt (n^ - n) / 2 ergibt. Sprich für meinen Wert n = 5 wäre es: (5^2 - 5) / 2 = 10. Was ja auch korrekt ist...

Nur: Was hat der kleine Gauss damit zu tun? also sprich die Formel i=0 Sigma n = (n (n+1)) / 2

Irgendwie will mir das alles noch nicht so recht einleuchten

-------------------------------------------------------------------------------------------------------------
Edit: Ein anderes Beispiel wäre das hier:
http://www8.pic-upload.de/30.08.11/7hy6urf6xa.jpg
Mir will einfach nicht einleuchten, wie man auf dem (rot unterstrichenen) Teil kommt:
http://www8.pic-upload.de/30.08.11/qwul6zevp66.jpg
Also besonders der Teil wo es auf einmal heißt: j=1 Sigma n+1 j

Viel mehr Beispiele/Erklärungen, ausser 2-3 einfache Beispiele, sind in meinen Unterlagen nicht enhalten und suche mich schon dumm und dämlich :/

SlaterB · 30. Aug 2011

b1zarRe hat gesagt.:
@SlaterB
auf n*n + 9 komme ich deshalb, weil die äußere Schleife n mal durchlaufen wird und die innere(in dem Beispiel für den Wert: 6) n + 9. Da die beiden verschachtelt sind und nicht etwa nacheinander folgt: n * n + 9 = n^2 + 9 = O(n^2). Wären die beiden Schleifen nacheinander, dann wäre es 2n + 9, richtig.

wenn du beide Zahlen multiplizierst, dann doch n * (n+9) = n^2 + 9n ?
wobei das auch nicht günstig ist, denn die n+9 sind ja bereits mehrere innere Durchläufe, nicht für jeden äußeren Durchlauf neu,
im Grunde kannst du nur ableiten, dass du aktuell n+9 innere Schritte bzw. 2n+9 Schritte insgesamt hast,
dass das n^2 ist, ist daraus eher nicht zu erkennen,

Nur: Was hat der kleine Gauss damit zu tun? also sprich die Formel i=0 Sigma n = (n (n+1)) / 2

nun, die innere Schleife verhält sich genau so wie die Summe über i, und dass ist eben diese tolle n^2-Formel,
was dir exakt hilft Komplexität n^2 abzuleiten, fertig,

wäre günstig wenn man das weiß, ansonsten wie gesagt durch Zählen bzw. Erkennen der doppelten Schleifen eigentlich auch zu lösen

b1zarRe hat gesagt.:
Mir will einfach nicht einleuchten, wie man auf dem (rot unterstrichenen) Teil kommt:

der erste Teil ist gegeben, der zweite mit Summe j ist eine halbwegs geschickte Umformung,
sowas kann man kaum lernen,
wichtig ist wieder dass hier exakt dieselbe Formelumwandlung für die Summe benutzt wird,
dass du das gleich als Bild/ Beispiel postest zeigt, wie wichtig diese Formel ist

also die solltest du dir schon merken, die ist Grundwissen in diesem Gebiet,

wenn man die Formel kennt und die alle erste gegebene i-Formel sieht (die man natürlich schon selber aus dem Code ableiten muss),
dann ist es nicht mehr ganz so verwegen, auf die Summe-j-Formel zu kommen,
was da passiert verstehst du hoffentlich,
der Rest ist dann Anwendung dieser Summe = n²/2 -Umwandlung + noch bisschen rechnen

b1zarRe · 31. Aug 2011

"wenn du beide Zahlen multiplizierst, dann doch n * (n+9) = n^2 + 9n ?"
-> stimmt, hast du recht! Dennoch bleibt es bei O(n^2) würde ich behaupten... Ich schaue mir gleich aber nochmal die Aufgabe an.

Zu der letzt gestellten Aufgabe habe ich folgendes herausbekommen:
Äußere Schleife läuft von 0,...,n-1,n also genau n+1 mal (mit i)
und die Innere Schleife läuft jedes i mithilfe von j die Werte:
0,...,i Also i + 1 Durchläufe.
Ich habe das mit dem Testwert n=4 geprüft und siehe da es stimmt... die Äußere Schleife läuft
genau 5x durch(also n+1 mal) und die Innere für jedes i genau i+1mal.

Nun ist die Frage, ob ich sagen kann (n+1) * (i+1) oder ob ich das i irgendwie "ersetzen" muss durch ein n, weil das ja alles von n abhängt? Ich kann zb. ableiten, dass i bei jedem mal um eins größer wird. Bei meinem Testversuch kamen die Werte 1(mal durchlaufen von innererSchleife),2(durchlaufen innere Schleife),3,4,5. Da n = 4 ist.. kann ich dann sagen, dass die innere Schleife n+1 durchläuft? Und somit (n+1)*(n+1) => O(n^2) ??? Oder mache ich da murks und muss mit i weiterarbeiten? ODER muss ich wie bei der äußeren Schleife alle Durchläufe zusammenzählen? dann hätte ich für das Beispiel 15 heraus... und könnte die Formel ableiten:
n + 1 * (n^2 - 1) -> O(n^2)

Die Formel mit dem 2. Sigma will mir einfach nicht einleuchten =( vielleicht hat einer noch eine Erklärung für Dummies... Rest ist soweit klaro. Danke schonma

EDIT: Ich glaube ich habe es nun begriffen... Also nochmal:
Außen mithilfe i wird die Schleife 0,...,n-1,n also n+1 durchlaufen
für jedes i wird mithilfe j die inere Schleife 0,....,i-1,i also i+1 durchlaufen!
Nun habe ich mir den Testwert 4 genommen und habe eine Verlaufstabelle des Algorithmus aufgestellt mit folgendem Ergebnis: Äußere Schleife wird 5 durchlaufen (also n+1) und die innere durchläuft in jedem Durchlauf ein Schritt mehr... Zusammengezählt hatte ich ingesamt 15 Durchläufe. Wenn ich nun das Sigma mit 1 Start und bis n+1 aufstelle(also inere Schleife) dann erhalte ich mit dem Gauss die Formel: ((n+1) * (n+2)) / 2 und somit 1/2n^2 + 3^2n + 1 also O(n^2).

Ist dies ok so? Gauss darf man aber nur benutzen mit Start 1 bis n oder? Wie hätte ich das gemacht, wenn Start zb. 2 oder 3 wäre?! Sprich, wie könnte ich das alles lösen ohne dieses Sigma Zeichen und so... Ich habe alles mit abzählen gemacht ist das auch ok?

SlaterB · 31. Aug 2011

Start 2 oder 3 oder wenn hinten ein n fehlt ist nicht so tragisch, dann ergänzt du die restlichen Summen-Glieder und hast außerhalb zum Ausgleich eben noch -2 oder -n (genau wie eigentlich an anderen Stellen auch wenn man Mathe anwendet..)
wenn du durch die Summenformel auf n^2 kommst dann sind solche Konstanten oder linearen Faktoren letztlich egal

auch wenn es nicht unbedingt die ganze Formel gibt, wenn du z.B. 1, 3, 5, 7, 9, .. addierst dann ist das immer noch sowas wie n, bzw. n^2 in der doppelten Schleife, vielleicht nicht n^2 / 2 sondern n^2 / 4, aber der Faktor fällt letzlich ja weg

generell kann man nicht alles zusammenfassen, ich vermute z.B. nicht die Summe der Quadrate: 1, 4, 9, 16, 25, .. dort wird irgendwann der Abstand zwischen den Glieder so groß, dass das dann nicht mehr n^2 / c ist, vielleicht was kleineres wie n log (n)

immer und wirklich immer gilt: einfach ausprobieren/ ausrechen/ am PC zählen lassen
was für bestimmte n rauskommt, du bist nach wie vor bei 4, ich sage dir nach wie vor nimm 4000 oder noch höher,
nur hohe Zahlen lassen konstante Randeffekte verschwinden

noch ein Tipp zu Gauss:

Code:

         /|
      /   |
   /      |
/         |
----------

das anwachsende i ergibt das Dreieck mit Fläche n^2/2, genau die Hälfte des Quadrats n^2

b1zarRe · 31. Aug 2011

Und zu Aufgabe 2.2
Habe ich noch das hier gefunden: http://www8.pic-upload.de/31.08.11/cih5nlczh435.jpg

Ist das nicht totaler Murks? Hier werden auf einmal alle Werte zusammengezählt (innere Schleife nichtmal beachtet?!) und daraus eine Formel aufgestellt. Und nicht etwa die Anzahl der Schleifendurchläufe sondern die Variable k zusammenaddiert oO

Ich glaube ich komme schon näher das Thema zu verstehen, jedoch sind bei mir noch Unsicherheiten, wann ich Gauss aufstelle, ob ich das auch anders belegen kann ohne die Formel(durch reines Zählen), ob ich nun die Anzahl Durchläufe zählen muss oder die Werte zusammenzählen muss und wann so etwas kommen könnte wie nlogn oder logn

@SlaterB
hast du vielleicht 3-4 "Tutorials" oder würdest welche machen die zb. n, n^2 und irgendetwas anderes wie logn erläutern? Weiß echt nichtmehr was ich noch lesen kann oder was ich machen soll :/

b1zarRe · 31. Aug 2011

bitte löschen.. sorry

SlaterB · 31. Aug 2011

> Ist das nicht totaler Murks? Hier werden auf einmal alle Werte zusammengezählt
das du endlich mal zählen sollst sage ich dir doch von Anfang an und machst du ja auch,
und steht sogar mehr oder weniger in der Aufgabe, ok, da ist sicher letztlich eine Formel gewünscht,
ich weiß nicht was du dagegen hast,

und es wird das richtige gezählt, für k = 8 bzw. alle betrachteten k gibt es 4 äußere Schleifen, das enspricht den 4 Zeilen untereinander,
es gibt es für k=8 8 Schritte in der inneren Schleife, dann 4, 2, 1, steht alles da, es kommen genau 15 Schritte raus, richtig,
die 4 äußere Schleifen gehören als +4 gar nicht dazu, so ist das schon besser,

von dort aus auf die Formel 2k - log2(k) zu schließen ist sicherlich kühn,
da helfen die Werte nicht wirklich, da wurde eher die Formel an sich angeschaut,

ich wäre wieder zu k = 1000 gegangen -> Ergebnis 1994 Schritte, damit ist 2*k ziemlich deutlich,
was verloren geht muss man an der Struktur erkennen, bei jedem / 2 kann etwas verloren gehen (9/2 ist dasselbe wie 8/2),
es gibt genau so viele Divisionen wie 2er Faktoren, also Binärstellen, log2 interessant, das ist reichlich kompliziert,
eine exakte Formel ist deshalb auch kaum möglich, 2k - log2(k) ist jedenfalls keine sondern wie genannt ein bester Fall, Minimum,

hier sieht man übrigens wie eine Gauss-ähnliche Summe mit 1, 2, 4, 8, 16, .. nicht zu k^2 führt sondern gerademal 2*k,
was natürlich auch eine relativ bekannte Summe ist,
in einem KO-Pokal mit 64 Mannschaften, also 64 Spiele + 32 Spiele + 16 Spiele usw. gibts immer exakt 2*Mannschaften -1 Spiele
oder genau 2*Mannschaften Spiele, wenn auch Spiel um Platz 3

da ich gerade ein Programm habe, kann ich auch meine Quadrat-Anstiege, also 1, 4, 9, 16, .. testen,
geht bei k=1000 nur 496, bei 10000 nur bis 4950, ziemlich deutlich

b1zarRe · 31. Aug 2011

Jo, sorry vielleicht für dumme Fragen, aber an dem Thema hänge ich schon Wochen... Habe das aber mit dem genannten Beispiel(mit 8,4,2,1) verstanden.

Also zusammenfassend kann ich doch sagen: Egal wieviele Schleifen ich habe... ich gucke wie oft jede einzelne durchgeht, versuche daraus eine Formel in Betracht auf n zu bilden und falls diese Schleifen ineinander geschachtelt sind multiplizere ich die jeweiligen Ergebnisse der Schleifen und komme dann auf eine Formel womit ich Landau O bestimmen kann, richtig?
Und die GaussFormel brauche ich nicht unbedingt, da ich für kleinere Werte auch so O bestimmen kann, right?

Wäre dennoch dankbar, wenn jemand noch paar Beispiele postet... wäre echt mega... in der letzten Klausur kam eher was leichteres dran mit nur einer Schleife und am Ende O(n) (Suche in einem Array), aber ich würde gerne soviel wie es nur geht darüber verstehen.

SlaterB · 31. Aug 2011

> multiplizere ich die jeweiligen Ergebnisse der Schleifen und komme dann auf eine Formel womit ich Landau O bestimmen kann, richtig?

richtig multiplizieren kann man ja nie oder welches Beispiel meinst du von den genannten?,
an den bisherigen Beispielen sieht man letztlich eher dass das mit Vorsicht zu machen ist

wenn die äußere Schleife bis n einzeln verläuft und die innere da auch 'jede Menge bis n macht' dann kann wie bei Gauss n^2 rauskommen,
aber andere Schleifen sind dünner gesäht und dann kommt tatsächlich auch nurmal 2k, also k bzw. n raus, nicht k^2 bzw. n^2,

leicht ist es nicht, wenn es nur ein Teilgebiet ist würde ich dir langsam raten darauf zu verzichten,
wenn es zentrales Thema ist, dann musst du irgendwie wirklich noch schlauer werden,
aber mehr kann ich langsam nicht mehr schreiben, da musst du wirklich noch andere finden

b1zarRe · 31. Aug 2011

Naja zum Beispiel diese hier:

Java:

for(int i = 0; i <= n; i++) {
    //(...)
    
    for(int j = 0; j <= m; j++) {
         //(...)
    }
}

Könnte ich doch schlussfolgern das Außen n+1 und innen m+1 Durchläufe gemacht werden könnten. Also (n+1)*(m+1) =
nm + n + m + 1. Wie kann ich hierbei O bestimmen? Wenn n = m wäre, wäre es ja O(n^2), ist es aber nicht, also O(n) ???

Anderes Beispiel: (mit a < n)

Java:

int i = a;
while(i <= n) {
        //(...)
        i++;
}

-> While Schleife durchläuft die Werte i,i+1,...,n-1,n -> also n-i+1 Durchlauf. Ist das also dann O(n)? Oder wie kann ich das noch umschreiben?!

SlaterB · 31. Aug 2011

> Wenn n = m wäre, wäre es ja O(n^2), ist es aber nicht, also O(n) ???

gut, da mag die Multiplikation gehen, wenn m auch eine Variable ist, dann ist die Komplexität eben O(n*m),
wenn m konstant ist, dann O(n), richtig, dann kann man ja auch den kompletten inneren Block eine gewisse konstante Arbeit x sehen,
über die n-mal iteriert wird,
alle bisher hier genannten Beispiel waren ja interessanter mit von n abhängigen inneren Aktionen

unten O(n) von mir aus ja, falls nicht wieder a verdoppelt wird oder so, davon hängt es ja auch ab,
und eher while(a <= n) ? und was macht i?

b1zarRe · 31. Aug 2011

unten O(n) von mir aus ja, falls nicht wieder a verdoppelt wird oder so, davon hängt es ja auch ab,
und eher while(a <= n) ? und was macht i?

Jo, sorry habe es gerade verbessert!
Okay, soweit sogut.. Ich habe das obere mal nachprogrammiert, also hier am besten:

Java:

    public static void berechne2Schleifen(int n, int m) {
        int schleifendurchlaeufe1 = 0;
        int schleifendurchlaeufe2 = 0;
        
        for(int i = 0; i <= n; i++) {
            //(...)
            schleifendurchlaeufe1++;
            System.out.println("Schleife1");
            
            for(int j = 0; j <= m; j++) {
                //(...)
                schleifendurchlaeufe2++;
                System.out.println("Schleife2");
            }
        }
        System.out.println("Schleifendurchlaeufe1: " + schleifendurchlaeufe1);
        System.out.println("Schleifendurchlaeufe2: " + schleifendurchlaeufe2);
    }
    
    /** Tests */
    public static void main(String[] args) {
        
        System.out.println("berechne2Schleifen:");
        berechne2Schleifen(100,101);
        System.out.println("");

Und zum Beispiel herausbekommen... das bei berechne2Schleifen(2,3) 3mal die Äußere durchlaufen wird(also n+1) und die innere Schleife 12mal. Nur, was mache ich nun mit den Werten?

Und jaaa

ich habe auch höhere Werte genommen also zb berechne2Schleifen(100,101)
dort kam heraus das: äußere Schleife = 101 mal besucht wird und innere: 10302 also 101 * 102 (n+1 * m+1)... Darf ich dann schreiben O(n * m) gibt es so eine Klasse??

SlaterB · 31. Aug 2011

> 3mal die Äußere durchlaufen wird(also n+1) und die innere Schleife 12mal. Nur, was mache ich nun mit den Werten?
die äußeren Durchläufe kannst du bei allen bisherigen Beispielen wirklich vergessen,
und 12 ist genau 3*4 = n*m bzw. die +1-Versionen davon

O(n*m) geht meiner Meinung nach

b1zarRe · 31. Aug 2011

Ich habe mir noch ein eigenes Beispiel gemacht, hier in ausführlich:

Java:

int i = 0;

while(i < n) {
        
         int j = 2;
         while(j <= m + i) {
                 j++;  
         }
         i++;
}

1. Ich betrachte die Schleifen: Die Äußere läuft für i die Werte: 0,...,n-2,n-1 also: n-1+1 = n-mal durch! Die Innere Schleife läuft für ein i mithilfe j die Werte: 2,...,m+i-1,m+i durch.

2. Ich habe nun eine Verlaufstabelle aufgestellt, um zu schauen, was das für gewisse Werte bedeutet; Hier zur Veranschaulichung mit kleinen Werten n=5 und m=5(könnten aber auch unterschiedliche Werte sein): http://www8.pic-upload.de/31.08.11/envnzg5s93k7.jpg

Es ergibt sich, dass die Äußere Schleife tatsächlich n-mal durchläuft(also genau 5 mal)
und die innere Schleife läuft für jede Äußere Schleife genau m+i-1.(hier genau 30 mal)

Frage:
Ich weiß, ich könnte sagen, dass wenn n = m gilt, dass der Aufwand n * n+i-1 wäre und somit
O(n^2).
Was ist aber, wenn n != m, Kann ich dafür sagen, dass der gesamte Aufwand des Algorithmus (n) * (m+i-1) ist? Oder wie könnte ich das einschätzen?

SlaterB · 31. Aug 2011

i musst du vergessen, es geht immer letztlich nur um n bzw. hier n + m,
in diesem Fall kann man grob überschlagen, dass die innere Schleife linear zu m+n geht,
würde das m fehlen wäre es wieder was Gausartiges, also n, ob nun durch 2 usw. ist letztlich egal,
hier kommt noch m dazu, insgesamt dann meiner Ansicht nach n*(n+m),

b1zarRe · 1. Sep 2011

Ich verstehebleider nicht wie du auf n+m kommst?

SlaterB · 1. Sep 2011

wie gesagt: j<= i wäre nach Gauss etwa n, weil i ja von n abhängt und nicht zu lückenhaft ist,
dazu kommt noch m, denn es ist ja j <=i+m

im Zweifel immer zählen:

Java:

public class Test {
    public static void main(String[] args)  {
        int n = 1000;
        int m = 30;
        int c = 0;
        int i = 0;

        while (i < n)    {
            int j = 2;
            while (j <= m + i) {
                j++;
                c++;
            }
            i++;
        }
        System.out.println(c);
        System.out.println(n * (n + m));
    }
}

Augabe:

Code:

528500
1030000

das für sich sagt noch nicht viel, aber du kannst du Faktoren beliebig ändern, 0en ranhängen, streichen, lieber großes n und kleines m verwenden oder beide gleich groß,
die Zähung wird immer etwa gleich n * (n + m) sein oder bis zu 50% darunter, wegen Gauß ja eigentlich n/2,
das ist jetzt nicht gerade formal aber für mich ein ziemlich guter Nachweis für die Formel,

konstante Faktoren (auch begrenzt schwankend) spielen keine Rolle, im groben ist die Komplexität bestimmt,
jede andere Formel wie weiteres *log(m) oder noch drastischeres würde komplett andere Ergebnisse liefern,
auch kann weder n noch m weggelassen werden

b1zarRe · 4. Sep 2011

Noch einige andere Beispiele:

1.) Ich hatte ein Beispiel ausgerechnet, wo für die innere Schleife von n abhängig die Werte 8,4,2,1,0. Also (fast) immer Halbierung. Könnte man das umschreiben
mit 1/2n oder eher was log n artiges? Meiner Meinung nach eher 1/2n weil log n doch noch vieeel weniger ist als die Hälfte oder?

Hier die Aufgabe: (natürlich muss man schauen, ob gerade Werte oder ungerade durchlaufen werden)
http://www7.pic-upload.de/04.09.11/ntjo2tdpsofd.jpg

SlaterB · 4. Sep 2011

zum einen hättest du aus den bisherigen Beispielen schon lernen können, was bei Halbierung passiert,
schwer, aber zumindest was zu ahnen,
zum anderen gilt wie immer: zählen, und nicht für n = 4, sondern n = 10000

b1zarRe · 4. Sep 2011

Ok... also langsam habe ich, hoffe ich, geschnallt: Testwert zb. 100:
100,50,25,12,6,3,1 -> also bei n = 100 insgesamt 7 Durchläufe. Sprich: VIEL weniger als zb 100 was n-mal bedeuten würde. Weiter: Wenn sich Zahlen halbieren, kann man schon erahnen, dass es auf log n hinausläuft..?

Thanks

SlaterB · 4. Sep 2011

nach
http://www.java-forum.org/softwaree...tsanalyse-komplexitaetsklasse.html#post800596
vermute ich gerade Wurzel,

wie immer: hoch, höher, am höchsten, gehe auf 10.000, 100.000, 1 Mio. usw.,
was kommt an Zählung raus, was ist die Wurzel, was ist der Logarithmus?

besser wäre natürlich wenn man es sinnvoll erklären kann

b1zarRe · 4. Sep 2011

stimmt da hast Du recht.. jedoch hatten wir die Wurzelklasse garnicht in der Vorlesung besprochen und es sollen lediglich Themen aus der Vorlesung drankommen... wir hatten nur:

O(1)
O(log n)
O(n)
O(n log n)
O(n^2)
O(n^x)
O(n^n)

das wars.. zb auch kein O(n!)... aber gut, wenn ich das natürlich direkt sehe und sicher bin würde ich das auch sagen ja... andernfalls würde ich es den Klassen zuordnen die wir in der Vorlesung hatten.

SlaterB · 4. Sep 2011

wurzel n ist n^x mit einem bestimmten x, aber ich bin auch nicht so sicher ob nicht log(n),
also mehr kann ich dazu nicht sagen

Illuvatar · 4. Sep 2011

Sei x die gesuchte Laufzeit, dann gilt (bis auf das Abrunden, das macht aber qualitativ keinen Unterschied)
n * (1/2)^x = 1
Nach x auflösen: x = log(n) / log(2)
Also haben wir O(log n).

b1zarRe · 4. Sep 2011

@Illuvator: Danke Dir!

Noch eine Frage: Was wäre, wenn ich 2 Schleifen hätte, welche nacheinander geschrieben sind und die Variablen nicht gleich sind und nichts miteinadenr zu tun haben... also als Beispiel

Java:

int i = 0;
while(i <= n) {
   //(...)
   i++;
}

int j = 0;
while(j < m) {
   //(...)
   j++;
}

Das wäre ja dann sogesehen (n+1) * (m+1). Lässt sich das irgendwie noch zusammenfassen bzw. in welche Komplexitätsklasse gehört das? Schreibt man dann O((n) * (m))
oder lässt sich das irgendwie noch zusammenfassen!?

SlaterB · 4. Sep 2011

Logarithmus also doch, na ist doch schön, schlechter Tipp von mir, Zählung hätte es sicher geklärt

hier aber sicher richtig:
Multiplikation bei Verschachtelung, in deinem Code hintereinander ist Addition (wie wäre es stark zu belegen? ...

),
und kürzer als n+m gehts nicht, nein

b1zarRe · 5. Sep 2011

Ah ich idiot.. meinte +...... Ok thx leute!

b1zarRe · 5. Sep 2011

Leider doch noch eine Aufgabe die mich bisschen verzweifeln lässt:

Java:

for(int i = 0; i < n; i++) {
   int j = 0;

   while(j < i || a[i-j] == a[j]) {
      j++;
   }
}

Hierfür habe ich mir eine Verlaufstabelle gemacht und herauskam:
(Für Testwert n = 5)
5 Äußere Durchläufe und insgesamt 11 innere Durchläufe.

(Für Testwert n = 10)
10 Äußere Durchläufe und insgesamt 46 innere Durchläufe.

(Für Testwert n = 100)
100 Äußere Durchläufe und insgesamt 5051 innere Durchläufe.

(Für Testwert n = 1000)
1000 Äußere Durchläufe und insgesamt 500500 innere Durchläufe.

Folger ich hieraus richtig, dass der Aufwand insgesamt O(n^2) ist, da es immer ca (n^2) / 2 ist?

SlaterB · 5. Sep 2011

äußere Durchläufe interessieren nach wie vor nicht, der Rest klingt gut, was gibt es da zu verzweifeln?
das Beispiel gab es doch auch schon, abgesehen von dem Array-Vergleich, der aber anscheinend nie anspringt,
Rest ist eben der kleine Gauss

b1zarRe · 4. Okt 2011

D A N K E an alle die Fragen beantwortet haben und besonders an
XHELP und SlaterB!!!

Klausur war sehr erfolgreich und 1er Note

Laufzeitsanalyse und Komplexitätsklasse

Bekanntes Mitglied

SlaterB

Gast

Bekanntes Mitglied

SlaterB

Gast

Top Contributor

Bekanntes Mitglied

SlaterB

Gast

Top Contributor

Bekanntes Mitglied

SlaterB

Gast

Bekanntes Mitglied

SlaterB

Gast

Bekanntes Mitglied

Bekanntes Mitglied

SlaterB

Gast

Bekanntes Mitglied

SlaterB

Gast

Bekanntes Mitglied

SlaterB

Gast

Bekanntes Mitglied

SlaterB

Gast

Bekanntes Mitglied

SlaterB

Gast

Bekanntes Mitglied

SlaterB

Gast

Bekanntes Mitglied

SlaterB

Gast

Bekanntes Mitglied

SlaterB

Gast

Bekanntes Mitglied

SlaterB

Gast

Top Contributor

Bekanntes Mitglied

SlaterB

Gast

Bekanntes Mitglied

Bekanntes Mitglied

SlaterB

Gast

Bekanntes Mitglied