DokuWiki - fricklers.org

Trace:

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
Last revisionBoth sides next revision
repds15:fragen-antworten [2015/10/04 17:26] – [Fragen und Antworten] 95.222.28.193repds15:fragen-antworten [2015/10/04 18:20] – mario
Line 26: Line 26:
 </code> </code>
 </WRAP> </WRAP>
-**Antwort**: Die innere Schleife endet in jedem Durchlauf der äußeren Schleife nach spätestens $O(\log(n))$ Schritten wegen ''j=j*2'', wenn man j=1 als Startwert annimmt. Somit haben wir insgesamt $O(n \log(n))$ als obere Abschätzung. Die untere $\Omega$-Abschätzung kriegen wir, wenn wir nur "großen" Anteile der Laufzeit analysieren. Dafür gucken wir diesen leicht modifizierten Code an: +**Antwort**: Die innere Schleife endet in jedem Durchlauf der äußeren Schleife nach spätestens $O(\log(n))$ Schritten wegen ''j=j*2'', wenn man j=1 als Startwert annimmt. Somit haben wir insgesamt $O(n \log(n))$ als obere Abschätzung. Die untere $\Omega$-Abschätzung kriegen wir, wenn wir nur "großen" Anteile der Laufzeit analysieren. <del>Dafür gucken wir diesen leicht modifizierten Code an:</del> 
-<code>+<code> #### So nicht!!! Falsch!!! Mein Fehler, Gruß, Mario ##### 
 for ( i=1; i<n/2; i++) for ( i=1; i<n/2; i++)
   for ( j=n/2; j<n; j=j*2)   for ( j=n/2; j<n; j=j*2)
 </code> </code>
-Man kann sich überlegen, dass die äußere Schleife nun nur noch halb so oft läuft und die innere Schleife auch seltener. Dennoch erhalten wir $n/2 \cdot \log(n/2) = \Omega(n \log(n))$ als Laufzeit.  +<del>Man kann sich überlegen, dass die äußere Schleife nun nur noch halb so oft läuft und die innere Schleife auch seltener. Dennoch erhalten wir $n/2 \cdot \log(n/2) = \Omega(n \log(n))$ als Laufzeit. 
-Somit sind die obere und untere Schranke identisch und wir erhalten $\Theta(n \log(n))$ als Laufzeit.+Somit sind die obere und untere Schranke identisch und wir erhalten $\Theta(n \log(n))$ als Laufzeit.</del> 
 + 
 +**Achtung (Fehlerkorrektur)**: Mit dem modifizierten Code läuft die innere Schleife immer nur einmal. So kommt man nicht auf $n \log(n)$, sondern nur auf $n$ bzw. $n/2$. Besser man schreibt die Schleifen als Summenformel auf: $\sum_{i=1}^n \log(n-i) \approx \int_1^n \log(x) dx = \Theta(n \log(n))$
  
 **Folgefrage**:  **Folgefrage**: 
Line 52: Line 54:
 }              //  Aufruf f5(1000000) ergibt:   c: 1999986  i: 999999  j: 999999 }              //  Aufruf f5(1000000) ergibt:   c: 1999986  i: 999999  j: 999999
 </code> </code>
 +**"Antwort"**: Hmm, jetzt bin ich selbst verwundert. [[http://www.wolframalpha.com/input/?i=int+log_2%28x%29+dx|Wolframalpha]] bestätigt eigentlich die Analyse mit der Summenformel von oben. Hast du mal noch größere Werte ausprobiert?
 +
 +**"Re:Antwort"**:   f5(1000000000) ergibt:    c: 1999999977  i: 1000000000  j: 1999999998
 +
 +**"Re:Re:Antwort"**: Und die Initialisierung von i und j zu Beginn der Funktion sowie die fehlenden Klammer der i-Schleife machen wirklich nichts aus? Ich bin gerade mittelmäßig verwirrt, wieso die experimentellen Ergebnisse meine Summenformel-Analyse nicht zu bestätigen scheinen... :( Wie kann denn j im Code oben am Ende eine ungerade Zahl sein?
 ---- ----