elundril - Mi 01.04.09 21:48
Titel: Beweis der Laufzeit in O

---

Hallo,

ich soll zeigen das 10^n = O(n!) gilt indem ich konrekte werte für n0 und c finde und beweisen, dass die entsprechenden Ungleichungen mit diesen Konstanten erfüllt werden kann.

Ich hab das gelöst, indem ich die beiden in Excel eingetragen hab und nachgesehen hab wann 10^n größer wird als n!. Dadurch bin ich auf n0= 25 und c= 1 gekommen. Aber da gibts sicher nen schöneren weg, kann mir jemand erklären, wie man das schöner löst?

lg elundri

Bergmann89 - Do 02.04.09 01:51

---

HI,

n! is nix anderes als ne arithmnetische Folge, da kannste die summe berechnen:

S = (a1+ak)*n/2
S = (1+n)*n/2
S = n/2 + (n^2)/2

und das kannste ja dann in die Formel einsetzen:

f(n) = 10^n | g(n) = n! | n >= n0
f(n) = O(g(n))
f(n) <= c*g(n)
10^n <= c*(n/2 + (n^2)/2)

jetzt musste ja nur noch umformen, hilft dir das weiter?

MfG Bergmann.

AXMD - Do 02.04.09 08:38

---

Bergmann89 hat folgendes geschrieben :

n! is nix anderes als ne arithmnetische Folge, da kannste die summe berechnen

Ich kenne mich zwar mit Komplexitätstheorie nicht aus, aber n! ist ganz bestimmt keine arithmetische Folge und kann daher auch nicht als Summe geschrieben werden. n! ist auch keine geometrische Folge, da der Faktor zwischen den Gliedern linear anwächst und damit nicht konstant ist (wie er es bei einer geometrischen Folge sein müsste). Soweit mir bekannt steigt n! schneller als die meisten Exponentialfunktionen - rein mathematisch gesehen. In diesem Zusammehang könnte dir auch die Stirling-Formel [http://de.wikipedia.org/wiki/Stirling-Formel] weiterhelfen, da das zumindest annähernd zeigt, dass n! in etwa proportional zu n^n wächst. Inwiefern das aber mit der Komplexitätstheorie zusammenhängt kann ich wie erwähnt nicht sagen, da ich mich damit nicht auskenne.

AXMD

Gausi - Do 02.04.09 08:56

---

Man benötigt ja nur ein beliebiges n0 und ein beliebig großes c.

Wie wäre es also mit n0=10 und c=10^10? Dann ist für n > n0



Ließe sich zwar bestimmt auch schärfer abschätzen (einfach mal ein 10! unter den Tisch fallen lassen ist schon recht grob), aber das muss ja nicht sein. :mrgreen:

Edit: Man könnte auch c=10^10/10! ~ 2755 wählen, das wäre etwas greifbarer. ;-)

Thorsten83 - Do 02.04.09 09:50

---

Hey,

ich finde die Formulierung etwas gefährlich, "10^n liegt in O(n!)" oder "10^n € O(n!)" fände ich besser...

Ich würde einfach zeigen dass (10^n)/(n!) konvergiert...

Gausi - Do 02.04.09 10:06

---

@Thorsten83: Die Schreibweise f(n) = O(g(n)) ist zwar falsch bzw. mathematisch unsinnig, wenn man O(g) als Menge definiert, sie hat sich aber - besonders im amerikanischen - so eingebürgert. Oft wird dann O(g) nicht als eine Menge von Funktionen betrachtet, sondern man definiert einfach die Schreibweise "f = O(g)", wenn ...

elundril - Do 02.04.09 11:07

---

Thorsten83 hat folgendes geschrieben :

Hey, ich finde die Formulierung etwas gefährlich, "10^n liegt in O(n!)" oder "10^n € O(n!)" fände ich besser... Ich würde einfach zeigen dass (10^n)/(n!) konvergiert...

das heißt, Grenzwert n->unendlich (10^n)/(n!) oder? das heißt oben wird es unendlich und unten wird es unendlich. Das hieße doch ich müsste den Satz von de l'Hospital anwenden? hmm für n! gibts aber keine ableitung, deswegen muss ich die stirlin-Formel verwenden, die mir aber nur nen näherungswert liefert (was bei n ja egal ist wenn ich nix dafür einsetze), und die dann ableiten.

stimmt meine überlegung soweit?

lg elundril

Gausi - Do 02.04.09 11:19

---

Ich denke nicht, dass man hier mit dem Grenzwert arbeiten sollte.

Wie man mit etwas Überlegen ein passendes n0 und ein c finden kann, und dabei auch direkt beweist, dass das für alle größeren n auch so ist (was ja bei der Excel-Lösung erstmal nicht gegeben ist), habe ich ja oben gezeigt. :nixweiss:

Bergmann89 - Do 02.04.09 11:58

---

AXMD hat folgendes geschrieben :

n! ist ganz bestimmt keine arithmetische Folge und kann daher auch nicht als Summe geschrieben werden.

Sry, hab mich vertan, dachte n! = 1+2+...+n
Ich hätte vlt doch lieber ins bett gehen sollen, war ja schon spät^^

MfG Bergmann