Startseite » Forum » Logarthmen, Laufzeiten, Funktion

Logarthmen, Laufzeiten, Funktion

Universität / Fachhochschule

Sonstiges

Tags: Sonstiges

babadura aktiv_icon

14:58 Uhr, 10.03.2010

Guten Tag wünsche ich Euch! ;-)

Ich habe folgende Frage:

Ich muss mit Hilfe von Landau Notation (Groß

O

usw) mehrere Laufzeiten vergleichen. Und nun habe ich folgendes Problem mit folgenden 2 Laufzeiten.

n log (n)

und

(log (n))!

Wegen der Definition von Fakultät habe ich

(log (n))!

als als

⌈ log (n) ⌉!

gedeutet. Und nun habe ich ein Problem, ich glaube schon, dass

n log (n)

schneller steigt als

(log (n))!,

jedoch komme ich zu anderen Ergebnissen, wenn ich für die Logarithmen verschiedene Basen einsetze,

z . B

. für

{log}_{2}

scheint die

(log (n))!

schneller zu steigen als

n log (n),

was wiederum bei

{log}_{10}

anders ist. Und man kann sich auch nicht wirklich mit einer Konstante verhelfen. (Wobei hier kann ich durchaus falsch liegen). Ich glaube aber, dass die Einschätzung, welche Funktion nun schneller wächst doch unabhängig von der Basiswahl sein soll.

Meine Frage ist - wo denke ich falsch und kann mir jemand evtl. ein Tipp geben, in welche Richtung ich denken soll?

LG
Vika

Hierzu passend bei OnlineMathe:
Funktion (Mathematischer Grundbegriff)

johannes2010 aktiv_icon

16:54 Uhr, 10.03.2010

Bringt die die Stirling-Formel was?

n! \approx \sqrt{2 π n} \cdot {(\frac{n}{e})}^{n}

http//de.wikipedia.org/wiki/Stirling-Formel

babadura aktiv_icon

17:35 Uhr, 10.03.2010

hmm, ehrlich gesagt nicht wirklich, aber die Formel haben wir auch nicht in der Vorlesung gelernt. Ich meinte eher, wie man dies mit normalen "menschlichen" Mittlen zeigen könnte? Also, mit einfachen Rechenregeln? In welche Richtung ich da denken sollte?

johannes2010 aktiv_icon

18:05 Uhr, 10.03.2010

Ok. Vielleicht das: