Schnittpunkt einer quadratischen und loga Funktion berechnen

17.07.2011, 13:36

cod3r

Schnittpunkt einer quadratischen und loga Funktion berechnen

Meine Frage:
Ich habe da mal eine Frage. smile

Bei der Berechnung von Laufzeitschranken in der Informatik I stoße ich auf folgendes Problem:

Behauptung:
$\begin{eqnarray*} n^{2}-7n+5 = \Theta log(n^{n}) \end{eqnarray*}$

als Ausdruck:
$\begin{eqnarray*} a_{1}log(n^{n})\leq n^{2}-7n+5\leq a_{2}log(n^{n}) \end{eqnarray*}$

Meine Ideen:
Nun habe ich mir gedacht, dass ich als erstes die Schnittpunkte zwischen
$\begin{eqnarray*} f(n)=n^{2}-7n+5 \end{eqnarray*}$
und
$\begin{eqnarray*} g(n)=a*log(n^{n}) \end{eqnarray*}$
berechne damit ich nachher eingrenzen kann für welchen Bereich von $\begin{eqnarray*} x \end{eqnarray*}$ die Behauptung gilt.

Leider weiß ich im Moment nicht wie ich den Ansatz setzen soll, weil ich 2 Variablen habe. $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} x \end{eqnarray*}$ . Verständlich ist, das ich nach $\begin{eqnarray*} x \end{eqnarray*}$ auflösen muss, da ich ja die Schnittpunkte brauche, aber wie gehe ich mit der 2 Variablen $\begin{eqnarray*} a \end{eqnarray*}$ um?

17.07.2011, 15:58

Math1986

Auf diesen Beitrag antworten »

RE: Schnittpunkt einer quadratischen und loga Funktion berechnen

Zitat:

Original von cod3r
Meine Ideen:
Nun habe ich mir gedacht, dass ich als erstes die Schnittpunkte zwischen
$\begin{eqnarray*} f(n)=n^{2}-7n+5 \end{eqnarray*}$
und
$\begin{eqnarray*} g(n)=a*log(n^{n}) \end{eqnarray*}$
berechne damit ich nachher eingrenzen kann für welchen Bereich von $\begin{eqnarray*} x \end{eqnarray*}$ die Behauptung gilt.

Wo kommt dein $\begin{eqnarray*} x \end{eqnarray*}$ her?

Du kannst den Term vereinfachen durch
$\begin{eqnarray*} log(n^{n})=n\cdot log(n) \end{eqnarray*}$
also
$\begin{eqnarray*} a_1\cdot n\cdot log(n)\leq n^{2}-7n+5\leq a_2\cdot n\cdot log(n) \end{eqnarray*}$
somit
$\begin{eqnarray*} a_1\cdot log(n)\leq n-7+\frac 5n \leq a_2\cdot log(n) \end{eqnarray*}$

Neue Frage »

Antworten »

Schnittpunkt einer quadratischen und loga Funktion berechnen

Verwandte Themen