Discussion :

[Lithrein]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[prgasp77]

Bonjour,
je pense que la mise en équation contient une erreur. En effet, T(0, p) = O(1) pour tout p. Ceci n'est pas rendu par la seconde équation qui diverge donc.

Cdlt,

[Lithrein]

C'est en effet un oubli, merci de me l'avoir signalé.

[prgasp77]

Première piste :

(pour e et p non nul)

Je continue l'investigation.