Question théorique sur les structures de données
kyorinzo
Messages postés
13
Statut
Membre
-
KX Messages postés 19031 Statut Modérateur -
KX Messages postés 19031 Statut Modérateur -
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
A voir également:
- Question théorique sur les structures de données
- Fuite données maif - Guide
- Effacer les données de navigation sur android - Guide
- Trier des données excel - Guide
- Sauvegarde des données - Guide
- Que veut dire supprimer les données d'une application - Guide
1 réponse
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.
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.
