Analisi della complessità di M! / N! (M-N)!

Question

Dato il runtime di un algoritmo per essere m! / (n! * (m-n)!) Questo è MCN, dove sia M e N sono variabili, è il fattoriale di complessità o polinomiale?O è qualcos'altro?

Elaborare.

Grazie

Answer 1

Le crescite potrebbero essere lineari o costanti a seconda della relazione tra $ m $ e $ n $ mentre crescono grandi. Ad esempio, se $ N $ cresce con $ m $ come in $ M= N + 1 $ , quindi $ \ binom {m} {n}=binom {n + 1} {n}= n + 1 $ .

Ora, se sei interessato alla massima crescita, allora i coefficienti binomiali $ \ binom {m} {n} $ sono più grandi quando $ N $ è la metà della $ m $ . PUS $ M= 2N $ E UTILIZZARE Approssimazione di Stirling per il fattoriale. Ottieni

$$ \ binom {2n} {n}=frac {(2n)!} {(n!) ^ 2} {(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} $$