자바를 이용해서 알고리즘 문제를 풀거나 큰 사이즈의 데이터를 다룰 때, 컬렉션들의 정확한 시간복잡도(Big-O)를 알고 사용하는 것이 중요하다. 자칫 불필요하게 느린 컬렉션이나 메소드를 사용할 경우 예상치 못한 성능저하를 만날 수 있기 때문이다.
List
| add() | remove() | get() | contains() | |
| ArrayList | O(1) | O(n) | O(1) | O(n) |
| LinkedList | O(1) | O(1) | O(n) | O(n) |
| CopyOnWriteArrayList | O(n) | O(n) | O(1) | O(n) |
참고로 LinkedList의 삭제 연산인 remove() 메소드는 삭제할 노드에 대한 참조를 가지고 있다는 가정하에 O(1)임을 유의해야한다. 만약 처음부터 지울 데이터를 찾아야한다면 탐색 비용인 O(n)이 소요된다.
Set
| add() | contains() | next() | |
| HashSet | O(1) | O(1) | O(h/n) |
| LinkedHashSet | O(1) | O(1) | O(1) |
| EnumSet | O(1) | O(1) | O(1) |
| TreeSet | O(log n) | O(log n) | O(log n) |
| CopyOnWriteArraySet | O(n) | O(n) | O(1) |
| ConcurrentSkipList | O(log n) | O(log n) | O(1) |
HashSet에서 next() 메소드는 O(h/n) 시간 복잡도를 갖는다. h는 해시 버킷의 사이즈를 의미하고, n은 HashSet에 저장되는 데이터의 사이즈를 의미한다. h/n 이라는 값이 나오는 이유는 엘리먼트에 비해 해시버킷의 수가 늘어나면 해시버킷으로 사용되는 배열의 대부분은 비어있게 되고, 엘리먼트가 담겨있는 해시버킷을 찾기 위해 매번 비어있는 해시버킷을 방문해야하기 때문에 h가 들어간다. 또 한, 엘리먼트의 숫자가 늘어나면 해시 버킷이 비어있을 가능성이 줄어들게 되고, O(1)에 근접하게 된다. 이런 의미에서 h/n 이라는 시간복잡도가 나온 것으로 생각된다.
Queue
| offer() | peak() | poll() | size() | |
| PriorityQueue | O(log n) | O(1) | O(log n) | O(1) |
| LinkedList | O(1) | O(1) | O(1) | O(1) |
| ArrayDequeue | O(1) | O(1) | O(1) | O(1) |
| ConcurrentLinkedQueue | O(1) | O(1) | O(1) | O(n) |
| ArrayBlockingQueue | O(1) | O(1) | O(1) | O(1) |
| PriorityBlockingQueue | O(log n) | O(1) | O(log n) | O(1) |
| SynchronousQueue | O(1) | O(1) | O(1) | O(1) |
| DelayQueue | O(log n) | O(1) | O(log n) | O(1) |
| LinkedBlockingQueue | O(1) | O(1) | O(1) | O(1) |
Map
| get() | containsKey() | next() | |
| HashMap | O(1) | O(1) | O(h/n) |
| LinkedHashMap | O(1) | O(1) | O(1) |
| IdentityHashMap | O(1) | O(1) | O(h/n) |
| WeakHashMap | O(1) | O(1) | O(h/n) |
| 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) |
| ConcurrentSkipListMap | O(log n) | O(log n) | O(1) |
위에서 본 시간 복잡도는 Worst Case가 아닌 Amortized Analysis가 적용된 평균적인 값이다. 예를 들어 ArrayList의 add() 연산은 배열이 꽉 찾을 때 두 배 더 큰 새로운 배열에 엘리먼트들을 복사하는 최악의 경우가 있어서 O(n)으로 적어야 한다. 하지만 이 연산을 Amortize 하여 평균적으로 O(1)이라고 할 수 있는 것이다.
댓글