Complexités "Big O" pour les méthodes communes des collections Java et algorithmes de tri communs. ## Complexité (Du meilleur au pire) `O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)` ## Collections | `List` | Add | Remove | Get | Contains | Next | Data Structure | |------------------------|------|--------|------|----------|------|----------------| | `ArrayList` | O(1) | O(n) | O(1) | O(n) | O(1) | Array | | `LinkedList` | O(1) | O(1) | O(n) | O(n) | O(1) | Linked List | | `CopyOnWriteArrayList` | O(n) | O(n) | O(1) | O(n) | O(1) | Array | | `Set` | Add | Remove | Contains | Next | Size | Data Structure | |-------------------------|----------|----------|----------|----------|------|--------------------------| | `HashSet` | O(1) | O(1) | O(1) | O(h/n) | O(1) | Hash Table | | `LinkedHashSet` | O(1) | O(1) | O(1) | O(1) | O(1) | Hash Table + Linked List | | `EnumSet` | O(1) | O(1) | O(1) | O(1) | O(1) | Bit Vector | | `TreeSet` | O(log n) | O(log n) | O(log n) | O(log n) | O(1) | Red-black tree | | `CopyOnWriteArraySet` | O(n) | O(n) | O(n) | O(1) | O(1) | Array | | `ConcurrentSkipListSet` | O(log n) | O(log n) | O(log n) | O(1) | O(n) | Skip List | | `Queue` | Offer | Peek | Poll | Remove | Size | Data Structure | |---------------------------|----------|------|----------|--------|------|----------------| | `PriorityQueue` | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap | | `LinkedList` | O(1) | O(1) | O(1) | O(1) | O(1) | Array | | `ArrayDequeue` | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List | | `ConcurrentLinkedQueue` | O(1) | O(1) | O(1) | O(n) | O(n) | Linked List | | `ArrayBlockingQueue` | O(1) | O(1) | O(1) | O(n) | O(1) | Array | | `PriorirityBlockingQueue` | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap | | `SynchronousQueue` | O(1) | O(1) | O(1) | O(n) | O(1) | None! | | `DelayQueue` | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap | | `LinkedBlockingQueue` | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List | | Map | Get | ContainsKey | Next | Data Structure | |-----------------------|----------|-------------|----------|--------------------------| | HashMap | O(1) | O(1) | O(h/n) | Hash Table | | LinkedHashMap | O(1) | O(1) | O(1) | Hash Table + Linked List | | IdentityHashMap | O(1) | O(1) | O(h/n) | Array | | WeakHashMap | O(1) | O(1) | O(h/n) | Hash Table | | EnumMap | O(1) | O(1) | O(1) | Array | | TreeMap | O(log n) | O(log n) | O(log n) | Red-black tree | | ConcurrentHashMap | O(1) | O(1) | O(h/n) | Hash Tables | | ConcurrentSkipListMap | O(log n) | O(log n) | O(1) | Skip List | ## Algorithmes de tri | Algorithme | Meilleur | Moyenne | Le pire | [[Glossaire#Complexité en espace\|Complexité en espace]] | | -------------- | ---------- | ------------ | ------------ | ---------------------------------------------------------------- | | Quicksort | O(n log n) | O(n log n) | O(n^2) | O(log n) | | Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | | Timsort | O(n) | O(n log n) | O(n log n) | O(n) | | Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | | Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) | | Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) | | Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | | Tree Sort | O(n log n) | O(n log n) | O(n^2) | O(n) | | Shell Sort | O(n log n) | O(n log^2 n) | O(n log^2 n) | O(1) | | Bucket Sort | O(n+k) | O(n+k) | O(n^2) | O(n) | | Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | | Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | | Cubesort | O(n) | O(n log n) | O(n log n) | O(n) |