[알고리즘] 자료구조 시간복잡도 정리

따로 정리하는 것보다 따로 만들어진 글로 정리합니다.

시간복잡도 순서

시간복잡도 대표 표현식 위일수록 빠르다.
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)