n*log n = x nach n auflösen < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Das Beispiel hier ist aus Datenstruckturen und Algorithmen! Dennoch ist es ein Matheproblem das mich bremst!
Diese Aufgabe dient dazu das sie ein Gefühl für das Wachstum von Funktionen bekommen. Bestimmen sie für jede FUnktion f(n) und Zeit t in der folgenden Tabelle die maximale Problemgröße n_max(t) welche in der Zeit t berechnet werden kann, wenn man annimt das der Algorithums bei Inputgröße n, f(n) Mikrosekunden benötigt. Die mit x gekennzeichneten Kombinationen können Sie ausalssen Hier bezeichnen wir mit log n den Logarithums zur basis 2.
Meine Funktionen:
log(n)
n
n*log(n)
[mm] n^{2}
[/mm]
[mm] n^{3}
[/mm]
[mm] 2^{n} [/mm] |
Also die sache ist eigentlich ganz simple.
Ich kann in 1 sec [mm] 1*10^{6} [/mm] Schritte machen. Bei der funktion n sind das also 1 million Schritte in einer sekunde. Bei [mm] n^{2} [/mm] = [mm] 10^{6}
[/mm]
Das alles ist kein problem jedoch stoß ich halt hier an die grenze:
n*log(n) = [mm] 10^{6}
[/mm]
Wie in allerwelt soll ich das auflösen nutze ich das 2^ bleibt mir( [mm] 2^{n})^{log(n)}
[/mm]
auf jedenfall steh ich hier total an und es ist aus meiner sicht ein klares Matheproblem ich hoffe ich hab das ganze hier richtig reingestellt und hoffe es kann mir einer helfen.
|
|
| |
|
Hallo bonzai,
das kann man nicht auflösen, sondern nur eine numerische Näherung bestimmen. Die liegt hier bei etwa 62746,1265.
Grüße
reverend
|
|
|
| |
|
ich muss also für mehrere Zeiten das ganze berechnen 5 sec, 5h, 5 tage sowie 5 Jahre.
Da ich auch im verlaufe der Vorlesung noch öfters mit n*log(n) zutun haben werde wäre es für mich sehr interessant wie man diese Näherung bestimmt. Mir würde schon reichen wenn du mir ein online artikel postest wo ich das verfahren zur Bestimmung der Numerischen Näherung nachlesen kann :)
Ich denke mal ich sollte das dann schon hinkriegen ^^
|
|
|
| |
|
Hallo nochmal,
ich würde hier das Newton-Verfahren zur Interpolation von Nullstellen verwenden. Dazu findest Du viele Seiten im Netz, z.B. ![[]](/images/popup.gif) diese.
Grüße
reverend
|
|
|
|
