Differences

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

--- repds15:fragen-antworten [2015/10/04 15:52] – 94.219.213.151
+++ repds15:fragen-antworten [2015/10/04 18:20] – mario
@@ Line 26: / Line 26: @@
 </code>
 </WRAP>
-**Antwort**: Hier steht meine Antwort.
+**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?
 ----