Je vais peut-être bientôt enseigner un cours intensif sur Java. Bien qu’il soit probablement prudent de supposer que les membres du public connaîtront la notation Big-O, il n’est probablement pas prudent de supposer qu’ils sauront quel est l’ordre des différentes opérations sur les différentes implémentations de collections.
Je pourrais prendre le temps de générer moi-même une masortingce récapitulative, mais si elle existe déjà quelque part dans le domaine public, j’aimerais bien la réutiliser (avec le crédit approprié, bien sûr).
Quelqu’un a des conseils?
Ce site est plutôt bon mais non spécifique à Java: http://bigocheatsheet.com/
Les Javadocs de Sun pour chaque classe de collecte vous indiquent généralement exactement ce que vous voulez. HashMap , par exemple:
Cette implémentation fournit des performances à temps constant pour les opérations de base (get et put), en supposant que la fonction de hachage disperse correctement les éléments parmi les compartiments. L’itération sur les vues de collection nécessite du temps proportionnel à la “capacité” de l’instance HashMap (le nombre de compartiments) plus sa taille (le nombre de mappages clé-valeur).
TreeMap :
Cette implémentation fournit un coût de log (n) garanti pour la clé conteneur, permet d’effectuer, de mettre et de supprimer des opérations.
TreeSet :
Cette implémentation garantit un coût de log (n) garanti pour les opérations de base (append, supprimer et contenir).
(emphase le mien)
Le gars ci-dessus a donné une comparaison pour HashMap / HashSet vs TreeMap / TreeSet.
Je vais parler de ArrayList vs. LinkedList:
ArrayList:
get()
add()
ListIterator.add()
ou Iterator.remove()
, il sera O (n) pour déplacer tous les éléments suivants LinkedList:
get()
add()
ListIterator.add()
ou Iterator.remove()
, ce sera O (1)