eine Erklärung für exponentielle Zeitkomplexität des rekursiven Binomialkoeffizient in T (n)rekursive Kombination zeit Komplexität Analyse
int C(int n, int k){
if(n==k || k==0)return 1;
return C(n-1, k) + C(n-1, k-1);
}
T(a,b) die Anzahl der Male sein Lassen Sie funktionieren C(a,b) wird in der rekursiven Aufrufstruktur von C(n,k) genannt . Da C(a,b) von C(a+1,b) und C(a+1,b+1) aufgerufen wird (jedes Mal, wenn einer dieser 2 aufgerufen wird) erhalten wir T(a,b)=T(a+1,b)+T(a+1,b+1). Dies ist die Pascal's triangle formula: T s in der letzten Stufe der rekursiven Aufrufstruktur bildet die n ten Ebene des Dreiecks Pascal, und ist somit exponential mit n (Sperrung der Grenzfälle zB k=1 oder k=n, so beispielsweise k=n/2.).
Sie können Ihren Algorithmus O(n*k) Zeit machen, wenn Sie cache the results.
Sie addieren '1's, die durch die Stopp-Klausel erzeugt werden, bis zu etwas, das' O (n^min {k, nk}) 'ist, also benötigen Sie' Omega (n^{k, nk}) '-Summierungen . – amit