Discussion :

[sjrd]

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

d'avance