question théorique sur les structures de données Fermé

Question

Bonjour...!??
théoriquement la complexité de trie et de recherche dans un tableau est plus grande que celle du TAS,AVL et ABR mais dans les programme on trouve une contradiction en effet on trouve que le temps d'éxécution pour le tri dans un tableau est inférieure au celle des autres stucture et pafois vaut 0 µs
quelqu'un peut m'explique pourquoi cette contradiction ? et merci d'avance

KX · Answer

Déjà la complexité se calcule "au pire cas", parce que effectivement parfois tu peux tomber sur un cas facile qui renvoie le résultat immédiatement.

De toute façon, il ne faut pas mesurer la complexité avec le temps d'exécution.

Ce que l'on regarde c'est l'évolution, suivant la taille du problème, du nombre d'opérations élémentaires à effectuer. Mais selon la structure de données les opérations élémentaires peuvent être plus ou moins lourdes.

C'est pour ça que ce que l'on compare ce n'est pas la structure de données mais l'algorithme de parcours.

Par exemple une recherche par dichotomie dans un tableau est de même complexité que celle d'un arbre binaire de recherche.

Question théorique sur les structures de données

1 réponse

Discussions similaires