Wie kann die Binomialsumme effizienter berechnet werden?
Ich muss eine Gleichung wie folgt berechnen:
wok1,k2
sind gegeben. Ich benutze MATLAB, um @ zu berechnP
. Ich denke, ich habe eine korrekte Implementierung für die obige Gleichung. Meine Implementierung ist jedoch so langsam. Ich denke, das Problem ist der Binomialkoeffizient. Könnte ich aus der Gleichung einen effizienten Weg finden, um die Zeit zu verkürzen? Allen danken
Zumk1=150; k2=150; D=200;
, es braucht 11,6 Sekunden
function main
warning ('off');
function test_binom()
k1=150; k2=150; D=200; P=0;
for i=0:D-1
for j=0:i
if (i-j>k2||j>k1)
continue;
end
P=P+nchoosek(k1,j)*nchoosek(k2,i-j)/nchoosek((k1+k2),i);
end
end
end
f = @()test_binom();
timeit(f)
end
Update: Für die Zeitmessung habe ich festgestellt, dass nchoosek der Grund für die große Rechenzeit ist. Daher schreibe ich die Funktion wie folgt um
function re=choose(n, k)
if (k == 0)
re=1;
else
re=(n * choose(n - 1, k - 1)) / k;
end
end
Jetzt wird die Rechenzeit auf 0,25 Sekunden reduziert. Gibt es einen besseren Weg?