Résumé de Big-O pour les implémentations de Java Collections Framework ?

Question

Je peux enseigner un « crash-cours de Java » bientôt. Il est probablement sûr de supposer que les membres de l’auditoire sauront notation Big-O, il n’est probablement pas raisonnable de supposer qu’ils sauront ce que l’ordre des diverses opérations sur diverses implémentations de collection est.

J’ai pu prendre le temps de générer une matrice sommaire moi-même, mais si c’est déjà là dans le domaine public, quelque part, je voudrais bien la réutiliser (avec mention appropriée, bien sûr.)

Quelqu'un at-il des indications ?

Answer 1

Le livre de Java Génériques et Collections a cette information.

Le bas de la javadoc de la java.util paquet contient quelques bons liens:

• Vue d'ensemble des regroupements a un bon résumé de la table.
• De plan annoté la liste de toutes les implémentations sur une seule page.

Answer 2

Ce site est assez bon, mais pas spécifique à Java: http://bigocheatsheet.com/

Une copie de l'original link dans cette réponse peut être trouvée à http://javadevelopersenior.com/blog/wp-content/uploads/2013/05/java_collections.pdf

L'hébergement du site les liens d'origine de Java big-O résumé est maintenant hors ligne. Vous pouvez encore les trouver sur le site web de l'archive:

http://web.archive.org/web/20110227091351/http://www.coderfriendly.com/2009/05/12/java-collections-cheatsheet/

http://web.archive.org/web/20110626160836/http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf

Answer 3

La Javadoc de Sun pour chaque classe de collection seront généralement vous dire exactement ce que vous voulez. HashMap, par exemple:

Cette application fournit à constante de temps de la performance pour les opérations de base (get et put), en supposant que la fonction de hachage disperse les éléments correctement parmi les seaux. Itération sur les vues de la collection nécessite du temps proportionnel à la "capacité" de la table de hachage de l'instance (le nombre de seaux) ainsi que sa taille (le nombre de clé-valeur mappings).

TreeMap:

Cette application fournit la garantie log(n) coût du temps pour la containsKey, get, put et les opérations de suppression.

TreeSet:

Cette application fournit la garantie log(n) coût du temps pour les opérations de base (ajouter, supprimer et contient).

(l'emphase est mienne)

Answer 4

Le gars ci-dessus a donné comparaison pour HashMap / HashSet vs TreeMap / TreeSet.

Je vais parler de ArrayList vs LinkedList:

Liste de tableaux:

• O(1) get()
• amorti O(1) ajouter()
• si vous d'insérer ou de supprimer un élément dans le milieu à l'aide de ListIterator.ajouter() ou de l'Itérateur.remove(), il sera en O(n), de déplacer tous les éléments suivants

LinkedList:

• O(n) get()
• O(1) ajouter()
• si vous d'insérer ou de supprimer un élément dans le milieu à l'aide de ListIterator.ajouter() ou de l'Itérateur.remove(), il sera en O(1)

Answer 5

Voici un lien que j’ai trouvé pour être utile quand discussion certains objets Java très communs et combien leurs opérations coûtent à l’aide de la notation de Big-O.

http://objectissues.blogspot.com/2006/11/Big-o-notation-and-Java-constant-Time.html