Trace:
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
repds15:fragen-antworten [2015/10/04 18:11] – mario | repds15:fragen-antworten [Unknown date] (current) – removed - external edit (Unknown date) 127.0.0.1 | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Fragen und Antworten ====== | ||
- | Bitte setzt neue Fragen oben in das jeweilige Kapitel, damit die schon beantworten Fragen unten stehen. Bevor ihr eine Frage stellt, durchsucht bitte kurz diese Seite und die [[repds15: | ||
- | |||
- | **Vorlage: | ||
- | <WRAP round help> | ||
- | Hier steht meine Frage... | ||
- | |||
- | **Folgefrage**: | ||
- | </ | ||
- | **Antwort**: | ||
- | |||
- | ---- | ||
- | |||
- | **Laufzeit** | ||
- | <WRAP round help> | ||
- | Wie schätze ich die Laufzeit ab? | ||
- | |||
- | < | ||
- | i = n | ||
- | j = c = 0 | ||
- | |||
- | for ( i=1; i<n; i++) | ||
- | for ( j=i; j<n; j=j*2) | ||
- | print c | ||
- | </ | ||
- | </ | ||
- | **Antwort**: | ||
- | < | ||
- | for ( i=1; i<n/2; i++) | ||
- | for ( j=n/2; j<n; j=j*2) | ||
- | </ | ||
- | < | ||
- | Somit sind die obere und untere Schranke identisch und wir erhalten $\Theta(n \log(n))$ als Laufzeit.</ | ||
- | |||
- | **Achtung (Fehlerkorrektur)**: | ||
- | |||
- | **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. | ||
- | |||
- | < | ||
- | 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 << | ||
- | } | ||
- | } // Aufruf f5(1000000) ergibt: | ||
- | </ | ||
- | **" | ||
- | |||
- | **" | ||
- | |||
- | **" | ||
- | ---- | ||
- | |||
- | **Expansion** | ||
- | <WRAP round help> | ||
- | |||
- | Wenn wir nach der Expansion der Rekursionsgleichung beim kleinen Gauß landen, wissen wir ja dass die Laufzeit $n^2$ beträgt. Wie lautet die Laufzeit aber, wenn wir $i^k$ oder $a^i$ anstatt nur dem i haben? Bzw was könnte hier in der Klausur noch relevant sein? | ||
- | In der ersten Klausur war das Ergebnis dieser Aufgabe die geometrische Reihe mit Laufzeit $2^n$ | ||
- | </ | ||
- | Soll $i$ die Laufvariable der Summe sein? i=0,...,n? Falls ja: | ||
- | **Antwort**: | ||
- | Ansonsten hilft für Abschätzung oft [[http:// | ||
- | |||
- | ---- | ||
- | **Asymptotisches Wachstum** | ||
- | <WRAP round help> | ||
- | |||
- | Welche Funktion wächst schneller, $n!$ oder $n^{log_2n}$ ? | ||
- | </ | ||
- | **Antwort**: | ||
- | < | ||
- | from math import factorial, log2 | ||
- | |||
- | for i in range(1, 10000): | ||
- | a = factorial(i) | ||
- | b = i**log2(i) | ||
- | print(b/ | ||
- | </ | ||
- | |||
- | Darf man beide Seiten logarithmieren und dann vergleichen? | ||
- | **Antwort**: | ||
- | 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. | ||
- | |||
- | ---- | ||
- | |||
- | **Kantenbeziehungen: | ||
- | <WRAP round help> | ||
- | |||
- | Hier haben wir ja die Bedingungen besprochen für Querkanten, Vorwärtskanten und Rückwärtskanten. In dem Fall A[u]> | ||
- | </ | ||
- | **Antwort**: | ||
- | |||
- | ---- | ||
- | |||
- | **Master-Theorem, | ||
- | <WRAP round help> | ||
- | |||
- | Hier war die Nebenbedingung zu beachten: $a \cdot f(n/b) \leq \alpha \cdot f(n)$ und $0 < \alpha < 1$ | ||
- | |||
- | Was sagt diese Ungleichung aus? | ||
- | Gibt es ein Beispiel für den Fall, daß man den dritten Fall des Master-Theorems nicht anwenden kann, weil die Ungleichung nicht erfüllt ist? | ||
- | |||
- | </ | ||
- | **Antwort**: | ||
- | |||
- | **Beispiel**: | ||
- | |||
- | ---- | ||
- | ==== Logarithmen ==== | ||
- | <WRAP round help> | ||
- | - Wie berechne ich | ||
- | * $\log_{2}(n^4 + 3x)$ - hier macht mir das //3x// Probleme ;( | ||
- | * $\log_{10} (2/n^2)$ So scheint es nicht zu funktionieren: | ||
- | </ | ||
- | **Antwort**: | ||
- | * $\log_{2}(n^4 + 3x)$: Wenn das $x$ eine Konstante ist bzw. für die Laufzeitanalyse nicht beachtet werden soll (also die Theta-Notation nur in Abhängigkeit von $n$ benutzt wird), dann erhalten wir $\log_2(n^4 + 3x) = \Theta(\log_2(n^4)) = \Theta(\log(n))$. Falls es ein Schreibfehler war: $\log_2(n^4 + 3n) \leq \log_2(n^4 + n^4) = \log_2(2n^4) = \log_2(2) + \log_2(n^4) = 1 + 4 \log_2(n)$, wobei wir annehmen, dass $n$ groß genug für die Ungleichung ist. Das dürfen wir, da wir nur an einer asymptotischen Betrachtung interessiert sind. Außerdem erhalten wir $\log_{2}(n^4 + 3n) \geq \log_2(n^4) = 4 \log_2(n)$ und somit insgesamt: $4 \log_2(n) \leq \log_2(n^4 + 3n) \leq 1 + 4 \log_2(n)$. Nach unten und oben ist es durch einen $\Theta(log_2(n))$-Term beschränkt. | ||
- | * $\log_{10}(2/ |