따로 정리하는 것보다 따로 만들어진 글로 정리합니다.
시간복잡도 대표 표현식 위일수록 빠르다.
n : 자료구조 사이즈
빠른 순서 ↑
상수 시간 O(1)
로그시간 O(log N)
직선형 시간 O(N)
2차 시간 O(n^2)
지수 시간 O(C^n)
느린 순서 ↓
자료구조 : https://bangu4.tistory.com/202
자바 컬렉션 : https://www.grepiu.com/post/9
Stack
push : O(1)
pop : O(1)
peek(get) : O(n)
특징 : 삭제나 삽입시 맨 위에 데이터를 삽입하거나 삭제하기 때문에 시간복잡도는 늘 O(1) 의 시간복잡도를 가진다. 하지만 특정 데이터를 찾을 때는 특정 데이터를 찾을 때까지 수행을 해야하므로 O(n) 의 시간 복잡도를 가잔다.
Queue
(1) Enqueue : 큐 맨 뒤에 데이터 추가
(2) Dequeue : 큐 맨 앞쪽의 데이터 삭제
Enqueue : O(1)
Dequeue : O(1)
Search : O(n)
Deque
Deque : Double Ended Queue의 약어, 양쪽 끝에서 데이터의 삭제와 삽입 모두 가능한 구조의 큐
삽입: O(1)
삭제: O(1)(pop) / O(N)(remove)
검색: O(n)
ArrayList
add : O(1)
remove : O(n)
get : O(1)
Contains : O(n)
iterator.remove : O(n)
java 1.2에 추가, thread-safe 보장 안함
특징 : 데이터 추가,삭제를 위해 임시 배열을 생성해 데이터를 복사
- 대량의 자료를 추가/삭제시 복사가 일어 나게 되어 성능 저하를 일이킴
- 데이터의 인덱스를 가지고 있어 데이터 검색시 빠름
LinkedList
add : O(1)
remove : O(1)
get : O(n)
Contains : O(n)
iterator.remove : O(1)
java 1.2에 추가, thread-safe 보장 안함
특징 : 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있다.
- 데이터 추가/삭제시 빠름
- 데이터 검색시 처음부터 노드를 순화해야 되기 때문에 느림
HashMap
// HashMap
get : O(1)
containsKey : O(1)
next : O(h/n) h는 테이블 용량
java 1.2 에서 나옴
특징 : 순서에 상관없이 저장됨, Null을 허용한다. thread-safe 보장하지 않는다.
LinkedHashMap
get : O(1)
containsKey : O(1)
next : O(1)
java 1.4 에서 나옴
특징 : 순서대로 등록한다. Null을 허용한다. thread-safe 보장하지 않는다.
HashSet
add : O(1)
contains : O(1)
next : o(h/n) h는 테이블 용량
java 1.2 thread-safe 보장 안함
특징 : 객체들을 순서없이 저장하고 동일한 객체를 중복 저장하지 않는다.
- 중복되지 않는 값을 등록할때 용의
- 순서없이 저장되는것 주위
- null을 허용한다.
Black Red Tree
add : O(longN)
remove : O(longN)
get : O(longN)
선형탐색(순차접근) - O(N) // LinkedList get
랜덤탐색(임의접근) - O(1) // ArrayList get, ex) Array.get(i)
선택정렬, 버블정렬 - O(n^2)
삽입정렬 - 최선의 경우는 O(n), 평균과 최악의 경우 O(n^2)
쿽정렬, 병합정렬 - O(NlogN)
이진탐색 - O(logN)
DFS/BFS - O(V+E)