Komplexitätsanalyse von M! / N! (M-N)!

Question

Angesichts der Laufzeit eines Algorithmus zu sein m! / (n! * (M-N)!) Das ist MCN, in dem sowohl M als auch n Variablen sind, der Komplexitätsfaktor oder Polynom ist?Oder ist es etwas anderes?

bitte aufwendig.

danke

Answer 1

Die Wucherungen könnten je nach Beziehung zwischen $ M $ und $ n $ linear oder konstant sein wie sie groß werden. Wenn beispielsweise $ N $ mit $ M $ wie in $ m= n + 1 $ , dann $ \ Binom {m} {n}=Binom {n + 1} {n}= n + 1 $ .

Jetzt, wenn Sie sich für das maximale Wachstum interessieren, sind die Binomialkoeffizienten $ \ Binom {m} {n} $ bei $ N $ ist die Hälfte der $ M $ . Put $ M= 2N $ und verwenden Sie Die Annäherung von Stirling für das Fakultät. Du bekommst

$$ \ Binom {2n} {n}=frac {(2n)!} {(N!) ^ 2} \ SIM \ FRAC {(2n) ^ ^ 2n} E ^ {- 2n} \ sqrt {4n \ pi}} {n ^ {2n} e ^ {- 2n} 2n \ pi}=pi ^ {- 1/2} 2 ^ {2n} n ^ { -1/2} $$