Algorithme récursif et calcul de complexité
Bonjour,
En ce moment, je m'amuse sur un algorithme récursif que j'ai trouvé plutôt sympa et je me suis donc mis en tête de trouver sa complexité en temps. Cependant, cela s'avère un peu plus compliqué que prévu. En effet, je me retrouve avec une formule de récurrence que je vois pas du tout comment attaquer.
L'algorithme que j'ai ai le suivant, il permet de générer l'ensemble des parties à p éléments d'un ensemble :
Code:
1
2
3
4
5
6
7
|
let rec parties e p =
let add a l = a :: l in (* ajoute en tête de liste *)
if p = 0 then [[]]
else match e with
| [] −> []
| x :: xs −> List.map (add x) (parties xs (p - 1)) @ parties xs p |
J'obtiens alors la récurrence suivante que je ne sais résoudre :
T(e, p) = O(1) si p = 0
T(e, p) = O(1) si e = 0
T(e, p) = O(p) + T(e - 1, p) + T(e - 1, p - 1) * p
Merci d'avance pour votre aide.
