Résumé Big-O pour les implémentations du framework Java Collections? [fermé]

Je vais peut-être bientôt enseigner un "Java crash-course". Bien qu'il soit probablement sûr de supposer que les membres du public connaîtront la notation Big-O, il n'est probablement pas sûr de supposer qu'ils sauront quel est l'ordre des différentes opérations sur diverses implémentations de collection.

Je pourrais prendre le temps de générer moi-même une matrice de résumé, mais si elle est déjà dans le domaine public quelque part, j'aimerais bien la réutiliser (avec un crédit approprié, bien sûr.)

Quelqu'un a tout les pointeurs?

Author: Jared, 2009-02-18
Source

4 answers

Ce site est assez bon, mais pas spécifique à Java: http://bigocheatsheet.com/ Voici une image au cas où ce lien ne fonctionnerait pas

 127
Author: Ben J, 2017-11-28 19:47:10

Le livre Java Génériques et Collections a cette information (pages: 188, 211, 222, 240).

Liste des implémentations:

                      get  add  contains next remove(0) iterator.remove
ArrayList             O(1) O(1) O(n)     O(1) O(n)      O(n)
LinkedList            O(n) O(1) O(n)     O(1) O(1)      O(1)
CopyOnWrite-ArrayList O(1) O(n) O(n)     O(1) O(n)      O(n)

Définir les implémentations:

                      add      contains next     notes
HashSet               O(1)     O(1)     O(h/n)   h is the table capacity
LinkedHashSet         O(1)     O(1)     O(1) 
CopyOnWriteArraySet   O(n)     O(n)     O(1) 
EnumSet               O(1)     O(1)     O(1) 
TreeSet               O(log n) O(log n) O(log n)
ConcurrentSkipListSet O(log n) O(log n) O(1)

Implémentations de carte: 

                      get      containsKey next     Notes
HashMap               O(1)     O(1)        O(h/n)   h is the table capacity
LinkedHashMap         O(1)     O(1)        O(1) 
IdentityHashMap       O(1)     O(1)        O(h/n)   h is the table capacity 
EnumMap               O(1)     O(1)        O(1) 
TreeMap               O(log n) O(log n)    O(log n) 
ConcurrentHashMap     O(1)     O(1)        O(h/n)   h is the table capacity 
ConcurrentSkipListMap O(log n) O(log n)    O(1)

Implémentations de file d'attente: 

                      offer    peek poll     size
PriorityQueue         O(log n) O(1) O(log n) O(1)
ConcurrentLinkedQueue O(1)     O(1) O(1)     O(n)
ArrayBlockingQueue    O(1)     O(1) O(1)     O(1)
LinkedBlockingQueue   O(1)     O(1) O(1)     O(1)
PriorityBlockingQueue O(log n) O(1) O(log n) O(1)
DelayQueue            O(log n) O(1) O(log n) O(1)
LinkedList            O(1)     O(1) O(1)     O(1)
ArrayDeque            O(1)     O(1) O(1)     O(1)
LinkedBlockingDeque   O(1)     O(1) O(1)     O(1)

Le bas du javadoc pour le java.le paquet util contient de bons liens:

 172
Author: toolkit, 2018-01-27 20:28:15

Les Javadocs de Sun pour chaque classe de collection vous diront généralement exactement ce que vous voulez. HashMap, par exemple:

Cette implémentation fournit des performances en temps constant pour les opérations de base (get et put), en supposant que la fonction de hachage disperse correctement les éléments entre les compartiments. L'itération sur les vues de collection nécessite 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 log(n) time cost garanti pour les opérations containsKey, get, put et remove.

Ensemble d'arbres :

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

(emphase à moi)

 11
Author: matt b, 2009-02-18 04:31:55

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

Je vais parler de ArrayList vs. LinkedList:

ArrayList:

  • O (1) get()
  • amorti O(1) add()
  • si vous insérez ou supprimez un élément au milieu en utilisant ListIterator.add() ou Iterator.remove(), il sera O (n) pour décaler tous les éléments suivants

Liste de liens:

  • O (n) get()
  • O (1) add()
  • si vous insérez ou supprimez un élément moyen en utilisant ListIterator.add() ou Iterator.remove(), ce sera O (1)
 5
Author: newacct, 2018-02-09 12:51:36