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/09/21 16:36] – 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**: | ||
| - | |||
| - | ---- | ||
| - | |||
| - | ==== 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/ | ||