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 Hausaufgaben-Lösungsseite, damit es keine unnötige Arbeit gibt.

Vorlage:

Antwort: Hier steht meine Antwort.

Laufzeit

i = n
j = c = 0

for ( i=1; i<n; i++)
  for ( j=i; j<n; j=j*2)
     print c

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:

for ( i=1; i<n/2; i++)
  for ( j=n/2; j<n; j=j*2)

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.

Expansion

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 dieses nette PDF mit "useful inequalities".

Asymptotisches Wachstum

Antwort:

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?

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.

Kantenbeziehungen:

Antwort: Nein, A[u]>A[v] bedeutet, dass u später besucht wurde. Grafisch kannst du dir das so vorstellen, als würdest du mit deinem Ariadne-Faden um den Tiefensuchebaum herumlaufen und die Schritte zählen. Wenn du links von einem Knoten u bist, trägst du die Schrittzahl in A[u] ein, wenn du rechts neben dem Knoten u bist, trägst du E[u] ein. Siehe https://en.wikipedia.org/wiki/Tree_traversal

Master-Theorem, 3 Fall:

Antwort: $a \cdot f(n/b)$ ist der Aufwand, der für die $a$ rekursiven Aufrufe im nächsten Level des Rekursionsbaums anfällt. Angenommen die Nebenbedingung würde nicht gelten: $a \cdot f(n/b) > \alpha \cdot f(n)$. Dann ist es teurer, die $a$ rekursiven Aufrufe zu machen und entsprechend hält die Schranke $T(n) = \Theta(f(n))$ nicht mehr. Für das Theta brauchen wir dann auch $\alpha < 1$, damit die Summe der Laufzeiten aller rekursiven Aufrufe im ganzen Rekursionsbaum insgesamt die Form einer geometrischen Summe haben.

Beispiel: Wähle $a = b = 1$ und $f(n) = n$. Dann ist $f(n) = n = \Omega(n^\varepsilon)$ für jedes $0 < \varepsilon < 1$, aber $a \cdot f(n/b) = f(n) \leq \alpha \cdot f(n)$ gilt für kein $\alpha < 1$.

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/n^2)$: Die Rechnung stimmt. Der Logarithmus darf auch negativ sein, denn die Exponentialfunktion erlaubt auch negative Exponenten. Für das Thema Laufzeitanalyse macht das jedoch keinen Sinn.