 | Faktorielle Funktion |
|
Liebe Studierende, in Beantwortung der heute gestellten Frage: die Faktoriellenfunktion n! wächst stärker als als die Exponentialfunktion c^n, für jedes c, d.h. c^n = O(n!). Am leichtesten sieht man dies, wenn man für n>c den Quotienten n!/c^n = (1*2*...*(c-1)*c*(c+1)*...*n)/(c*c*...*c*c*c*...*c) = = (1/c)*(2/c)*....*((c-1)/c)*(c/c)*((c+1)/c)*....*(n/c) = (c!/c^c)*((c+1)/c)*....*(n/c) betrachtet. Der erste Faktor c!/c^c ist eine Konstante kleiner als 1, während im restlichen Produkt alle Faktoren größer 1 sind und nach oben unbeschränkt immer weiter wachsen. Das restliche Produkt wird also beliebig groß, insbesondere ab einem gewissen n größer als c^c/c!. Der Quotient n!/c>n ist damit für genügend großes n größer als 1, d.h. die Faktoriellenfunktion wächst stärker als c^n. Für den Spezialfall 2^n ist durch Induktion leicht beweisbar, dass ab eingem gewissen Startwert 2^n <= n! ist (Übung!). Beste Grüße, WS |
Formale Grundlagen 2 (WS 2006/07)
|