Repds15:fragen-antworten

This is an old revision of the document!

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

Vorlage:

Hier steht meine Frage…

Folgefrage: Hier steht noch eine Frage, weil mir die Antwort nicht gefällt oder ich noch weitere Fragen zum selben Thema habe.

Antwort: Hier steht meine Antwort.

Vorlage:

Master-Theorem, 3 Fall

Hier war die Nebenbedingung zu beachten: $a * f(n/b) \leq \alpha * f(n)$

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?

Folgefrage: Hier steht noch eine Frage, weil mir die Antwort nicht gefällt oder ich noch weitere Fragen zum selben Thema habe.

Antwort: Hier steht meine Antwort.

Logarithmen

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: $\log_{10}(2/n^2) = \log_{10}(2)-2 \cdot \log_{10}(n) = ?$

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.