Question théorique sur les structures de données
kyorinzo
Messages postés
9
Date d'inscription
Statut
Membre
Dernière intervention
-
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
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
- Supprimer les données de navigation - Guide
- Trier des données excel - Guide
- Comment sauvegarder toutes les données de mon téléphone - Guide
- Reinstaller windows sans perte de données - 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.