Citation :on visite chaque nœud au moins une fois, du coup l'appel PARCOURS-INFIXE(x) prend un temps
puisque l'arbre binaire contient n nœuds
Non, ceci montre seulement que tu fais au moins n opérations, donc un
.
Pour l'autre, ton raisonnement me semble un peu foireux en particulier ceci :
Citation :
On peut donc majorer le temps de parcours-infixe d'un noeud par 3
Donc si je suis au sommet de l'arbre et qu'il a
noeuds, je fais seulement 3 opérations pour parcourir l'arbre entier ?
Soit
le nombre d'opérations qu'il faut faire lors de l'exécution de PARCOURS-INFIXE lorsque l'argument est un arbre ayant
noeuds (feuilles et racine incluses), c'est-à-dire un arbre binaire ayant n niveaux de la racine aux feuilles.
On suppose qu'on fait sur sur chaque noeud un nombre u d'opérations.
En utilisant une relation de récurrence que je te laisse chercher, tu peux trouver la valeur exacte de C(n) en fonction de n et de u, et vérifier que c'est un
ce qui donne une complexité exponentielle en le nombre de niveaux, mais linéaire en le nombre de noeuds