[Complexité] Résolution d'une équation de récurrence (algo d'arbre)

Bonjour,

Le contexte

Dans le cadre d'un mini-projet de mon cours d'informatique (autant le dire tout de suite), j'ai développé un algorithme de "placement" d'arbre (pas forcément binaire). Le but étant de donner des positions aux noeuds de l'arbre, de façon à l'afficher de manière optimale (en minimisant l'espace requis en largeur).

L'algo fonctionne bien, et le projet tout autant. Mais pour "peaufiner" mon rapport, j'aimerais parvenir à déterminer la complexité de cet algorithme.

Ce que j'ai fait

Je suis bien parvenu à écrire mon équation de récurrence, ainsi qu'un certain nombre de relations importantes. J'ai également résolu les deux cas extrêmes : celui une racine à N-1 enfants qui eux-mêmes n'ont jamais d'enfant O(N) ; et celui où chaque noeud à 1 et 1 seul enfant, sauf celui tout en bas qui n'en a évidemment pas : O(N²).

La question

Comme tout ça est très dur à écrire dans un post de forum, j'ai attaché une page PDF qui sort de LaTeX, avec tout ce que j'ai su faire.

Par contre, je ne parviens pas à résoudre cette équation dans le cas général, et je n'ai aucune preuve que le cas 2 - celui en O(N²) - soit le pire cas :?

Si vous pouviez m'aider à me dépatouiller de ce léger problème, ce serait super chouette :ccool:

:merci: d'avance :)

salut

peux tu expliquer rapidement ce que fait ton algorithme (la fonction T ?)

Oui bien sûr.

Comme je l'ai dit, le but final est de donner des positions aux noeuds de l'arbre. En tout cas des positions en abscisses et relatives, par rapport à la position du parent du noeud. Et ce pour afficher l'arbre de la façon la plus étroite possible.

Chaque noeud X a donc un attribut xRelPos, qui est cette position par rapport à son parent. Ainsi que deux listes de valeurs lefts et rights qui sont ceci : pour chaque étage à partir de X, lefts contient la position (relativement à celle de X) du noeud le plus à gauche (parmi le sous-arbre dont la racine est X). De même, rights contient la position, à chaque étage, du noeud le plus à droite. Ces deux listes ont une longueur égale à la profondeur du sous-arbre dont la racine est X.

Mon algo, sur le noeud X, fait ceci :

1. Appliquer l'algo à tous les enfants de X.
2. Donner des positions relatives à ses enfants, les plus proches les uns des autres, mais en ne superposant pas la liste rights d'un enfant à la liste lefts de l'enfant qui le suit.
3. Calculer les listes lefts et rights de X, en fonction des positions données aux enfants, et de leurs listes lefts et rights.

Le cas de base de la récursion, c'est que les listes lefts et rights des noeuds feuilles contiennent toutes l'unique élément 0.0.
A la fin, on dit que la position relative de la racine est 0.0.

Le (1), c'est le T(ni, pi). Le (2), c'est en O(mP). Et le (3) est en O(P), ce qui est donc "écrasé" par le O(mP).

Est-ce que c'est clair ? Ou je réécris tout ça en pseudo-code ?

disons oui, précise, car tantôt tu parles de position et tantôt tu parles de listes...

Donc voici mon type de données principale :

Code:

---

1 2 3 4 5 6 7 8

Soit TNode un type record avec les champs : label: entier - Etiquette du noeud de l'arbre fils: array of TNode - liste des enfants du noeud posFromFirst: flottant - position par rapport au premier frère xRelPos: flottant - position en abscisse par rapport à son parent lefts: array of flottant - liste des positions les plus à gauche dans le sous-arbre rights: array of flottant - liste des pos les plus à droite dans le sous-arbre FinSoit

---

Fonction de traitement sur un noeud en général, qui est fonction récursive :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

procedure PlaceRelTree(Node: TNode) Si Node est une feuille de l'arbre (il n'a pas d'enfant) Alors Node.lefts <- [0.0] // tableau à 1 élément dont celui-ci est 0. Node.rights <- [0.0] Sinon PourTout Enfant dans Node.fils Faire PlaceRelTree(Enfant) FinPourTout (Node.lefts, Node.rights) <- PlaceChildren(Node.fils) FinSi FinProc

---

La fonction PlaceChildren est un peu complexe : elle va donner des valeurs correctes à posFromFirst et xRelPos pour chaque enfant.
Et je sais qu'elle est en O(m.P), sachant que m est le nombre de fils, et P la profondeur du sous-arbre dont la racine est Node.

salut

pour minorer et majorer tu peux dire
NF = nombre de feuilles

alors on a

P(P+1)/2 < X < P(P+1)/2*NF

où X est le nombre "d'instructions" exécutées et P la profondeur de l'arbre

Merci :) Donc globalement ce serait en Omega(P²) et en O(P²*NF). C'est déjà beaucoup plus précis que ma vague conjecture en O(N²) :D

Est-ce que tu pourrais expliquer un tout petit peu comment tu arrives à ce résultat, stp ?

salut

on regarde les étages de l'arbre: Mi nombre de noeuds du ième étage

(la racine est au 0 ième étage, ses fils au premier, leurs fils au deuxième ...)

ensuite on groupe les appels à PlaceChildren par l'étage du noeud (sa profondeur dans l'arbre)
et parmis ces noeuds on regarde celui qui a un sous arbre le plus profond

ensuite on majore tout ça (profondeur des sous arbres en dessous des noeuds de l'étage i, et nombre de noeuds de l'étage i)

on a donc P - i profondeur max sous un noeud du ième étage

et voila on fait la somme de tous les étages pour ça qu'on a P + P-1 + P-2...
= P (P + 1)

le nombre de noeud par étage étant majoré entre autre par le nombre de feuille

Super :D J'ai dû réfléchir un peu pour comprendre, mais j'y suis.

:merci: beaucoup pour ton aide :ccool:

:resolu: