arbres binaires meilleur parcours Fermé

Question

Bonjour,
G un projet concernant les arbres binaires, pour l'implémentation chainée et les parcours préfixe infixe et postfixe g pas de problème, mais j'arrive pas a calculer le temps d'exécution de chaque parcours et sous les 2 formes itératif et récursif(g 6 cas),on m'a dit que je devrais utiliser le clock,a savoir je travaille en c++.
et aussi quel est le meilleur parcours avec la justification.
je dois rendre ce mini projet demain. 
merci d'avance

KX · Answer

Calculer le temps d'exécution d'un algorithme ça ne se fait pas en secondes avec un chronomètre... Ça se fait mathématiquement, avec un calcul de complexité (généralement par récurrence)

Il faut considérer le pire cas et comparer pour chacune des méthodes le nombre d'opérations effectuées pour arriver au résultat

Pour le résultat ça dépendra de ce que tu veux faire avec ton parcours ? Est-ce que c'est pour compter le nombre d'éléments ? Pour voir si un élément existe ? Pour insérer un élément ?
Ça dépendra aussi de ton type d'arbre : trié ? équilibré ?

pont · Answer

Bonjour,

.  .Avec le "clock" c'est à dire l'horloge du processeur, tu ne peux faire cette mesure qu'en assembleur, pas en C++ qui ne donne pas les temps de chaque instruction, donc il faut que tu regardes le fichier compilé, et avec la data sheet du microprocesseur que tu utilises, tu trouveras exactement le temps mis, selon la vitesse de ton "clock" justement. Et bon courage! Je préfère que ce soit toi que moi qui ait ce travail à faire!
. .Cordialement


PS: tu parles de "récursif", alors s'il y a des milliers d'aller-retour, comment vas-tu faire? Et pour autant que tu aies la chance de sortir du puits de récursivité" !  J'espère que la mammie modératrice qui m'a à l'oeil me pardonnera si je dis que j'ai envie de rire?

Arbres binaires meilleur parcours

2 réponses

Discussions similaires