Comment évaluer combien de fois un algorithme est-il appelé ?
Bonjour!
J'ai eu un algorithme en cours et le professeur a demandé de trouver combien de fois serait-il appelé dans le cas suivant:
, C'est à dire dans le cas de la distribution binomiale de 
elements choisi parmi 
éléments avec 
leur probabilité d'apparaitre.
Code:
1
2
3
4
5
6
7
| double binomial1(int N, int k, double p) {
if (N == 0 && k == 0) return 1.0;
if (N < 0 || k < 0) return 0.0;
return (1.0 - p) * binomial1(N-1, k, p)
+ p * binomial1(N-1, k-1, p);
} |
La question était: combien de fois binomial1 serait il appeler pour évaluer binomial1(100, 50, 0.25) ?
j'ai d'abord tenté de mettre un system.out.println dans le code avec un indice incrementant à chaque fois que l'algorithme était appelé. J'ai remarqué que c'était une folie quand j'ai atteint
passed 2485266 times
TPuis je me suis demandé si ce n'était pas que 
fois, dès lors que l'algorithme est appelé deux fois à chaque tours? cependant, p*binomial1(N-1, k-1, p) semble n'être appelé que fois avec le paramètre 
...
