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/01 15:58] – 141.2.118.43repds15:fragen-antworten [2015/10/04 18:20] – mario
Line 12: Line 12:
  
 ---- ----
 +
 +**Laufzeit**
 +<WRAP round help>
 +Wie schätze ich die Laufzeit ab? 
 +
 +<code>
 +i = n
 +j = c = 0
 +
 +for ( i=1; i<n; i++)
 +  for ( j=i; j<n; j=j*2)
 +     print c
 +</code>
 +</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. <del>Dafür gucken wir diesen leicht modifizierten Code an:</del>
 +<code> #### So nicht!!! Falsch!!! Mein Fehler, Gruß, Mario ##### 
 +for ( i=1; i<n/2; i++)
 +  for ( j=n/2; j<n; j=j*2)
 +</code>
 +<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.</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**: 
 +Ich habe das mal codiert und war über das Ergebnis T(n)= 2n verwundert.
 +Für j=1 statt j=i stimmt jedoch $O(n \log n)$, was ich auch vermutet hatte.   
 +Vielleicht kann jemand den Code mal nachvollziehen. 
 +
 +<code>
 +void  f5 (int n)  // n = 1000000
 +{
 + int i = n;
 + int j = 0;
 + int c = 0;
 + {
 + for (  i = 1;   i < n; i++ )
 +                for ( j = i;   j < n; j *= 2 )
 +      { cout <<  "c: " << ++c <<  "  i: " << i <<  "  j: " << j <<  endl; }
 + }
 +}              //  Aufruf f5(1000000) ergibt:   c: 1999986  i: 999999  j: 999999
 +</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?
 +----
 +
 **Expansion** **Expansion**
 <WRAP round help> <WRAP round help>
Line 18: Line 67:
 In der ersten Klausur war das Ergebnis dieser Aufgabe die geometrische Reihe mit Laufzeit $2^n$ In der ersten Klausur war das Ergebnis dieser Aufgabe die geometrische Reihe mit Laufzeit $2^n$
 </WRAP> </WRAP>
 +Soll $i$ die Laufvariable der Summe sein? i=0,...,n? Falls ja:
 +**Antwort**: Bei $a^i$ hat man eine geometrische Summe. Statt $\sum_{i=1}^n i^k$ könnt ihr auch einfach das Integral $\int_{1}^n x^k dx$ ausrechnen.
 +Ansonsten hilft für Abschätzung oft [[http://www.lkozma.net/inequalities_cheat_sheet/ineq.pdf|dieses nette PDF mit "useful inequalities"]].
  
 ---- ----
Line 25: Line 77:
 Welche Funktion wächst schneller, $n!$ oder $n^{log_2n}$ ? Welche Funktion wächst schneller, $n!$ oder $n^{log_2n}$ ?
 </WRAP> </WRAP>
 +**Antwort**: 
 +<code>
 +from math import factorial, log2
 +
 +for i in range(1, 10000):
 +    a = factorial(i)
 +    b = i**log2(i)
 +    print(b/a)    # Das geht gegen 0. Was heißt das?
 +</code>
 +
 +Darf man beide Seiten logarithmieren und dann vergleichen?
 +**Antwort**: Das kann man machen, aber dann muss man aufpassen, dass man keine falschen Schlüsse zieht. Beispielsweise ist $2^{n/2} = o(2^n)$. Wenn man beide Seiten logarithmiert kommt man auf $n/2$ und $n$ und diese beiden Terme wachsen bekanntlich gleich schnell. Daraus kann man jedoch nicht auf das Wachstum von $2^{n/2}$ und $2^n$ schließen.
 +In der Aufgabe sieht das wie folgt aus: 
 +  * $\log(n!) = \sum_{i=1}^n \log(i) \approx \int_1^n \log(x) dx = \Theta(n \log(n))$
 +  * $\log(n^{\log(n)}) = \log(n) \cdot \log(n) = (\log(n))^2$
 +
 +Daraus kann man also wirklich schließen, dass $n!$ schneller wächst. 
 +
 ---- ----