Discussion :

[nicolas666]

Bonjour,

Dans le cadre d'un TD, je dois connaître la complexité d'un parcours en profondeur d'un arbre binaire localement complet. Est-ce que quelqu'un connaît cette complexité ? Merci d'avance à ceux qui pourront me répondre .


Nico.

[benratti]

Tu cherches la complexite en fonction de la profondeur de l'arbre ou du nombre de noeud ?

Complexite en fonction du nombre de noeud : o(n)
Complexite en fonction de la profondeur : o(e^n)

Je m'explique. Pour un parcours en profondeur, tu passes par un noeud un nombre lineaire de fois ( 1 fois quand tu arrives a ce noeud, dans ce cas, tu vas explorer le fils gauche, ensuite tu reviens a ce noeud, puis tu explores le fils droit, et tu reviens a ton noeud, donc dans tout les cas c'est lineaire )

Ensuite, la complexite en fonction de la profondeur est simple. Un arbre binaire complet de profondeur n contient 2^n noeuds donc un nombre exponentiel...

[nicolas666]

Merci pour le coup de pouce