Bonjour,
 
J'aurais voulu savoir si il y avait moyen de trouver sur le net les coups des principales operations du genre: chercher, inserer, supprimer un element pour differents types de structures: tableaux rangés et non rangés, listes chainés simples et doubles, tablea de hashage et autres..
J'ai pas mal de truc à implémenter et j'aimerais faire ca bien.. SI ca existe pas et si quelqu'un peut m'expliquer en vitesse comment calculer le temps d'execution, ca m'interesse encore plus!!!
 
Merci pour tout

recherche à ce sujet : complexité algorithmique
 
un début
http://en.wikipedia.org/wiki/Compu [...] ity_theory

Un cours la dessus :
http://www-id.imag.fr/Laboratoire/ [...] node6.html

ici aussi  
http://madchat.org/coding/algo/algo3_epfl.pdf

Salut,
 
Le coût de ces opérations est normalement asseez simple à trouver sur le net, voire à retrouver en réfléchissant un peu.
 
Un tableau permet d'accéder directement à n'importe quel élément, donc pour chercher un élément, s'il est trié le coût est O(log(n)) (recherche dichotomique). S'il n'est pas trié ou s'il s'agit d'une liste chaînée, le coût devient O(n) car on est obligé de parcourir tous les éléments.
 
Pour insérer ou supprimer un élément, le coût est constant pour la liste chaînée, et en O(n) pour le tableau car il faut déplacer tous ceux qui suivent.

tu parles ici du log binaire je pense log2(n)

Oui, oui, bien sûr. ;-)