TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 1

Aus VoWi
Zur Navigation springen Zur Suche springen

Zeigen Sie, dass gilt, indem sie konkrete Werte für und c finden und beweisen, dass die entsprechenden Ungleichungen mit diesen Konstanten erfüllt werden können.

Lösung[Bearbeiten | Quelltext bearbeiten]

Aus der Überlegung dass ist und ist muss das asympthotische Verhalten von n! entsprechend größer sein als .

Beweis durch wählen von einem gewissen Wert (z.B. n=30):

Überlegung[Bearbeiten | Quelltext bearbeiten]

Ab dem Wert 11 wächst die Permutation schneller als die Exponentialfunktion. Dh. der "Vorsprung" wird irgendwann eingeholt (bei 28). Andersrum könnte man das ganze auch mathematisch untermauern indem man für n! die Stirling-Näherungsformel einsetzt:

Nach einem Umformen wird man erkennen, dass ab n=10 die Permutation schneller wächst als die Exp.-Funktion. Was auch der einfachen Überlegung von vorhin entspricht.