요즘 구직 활동 하면서 실무면접을 보고 있는데 자꾸 대답을 못하거나 잘못 대답하는 경우가 많아서 대학 다니면서 공부했던 것들을 정리해보려고.
일단 자료구조별 시간복잡도에 대해서 정리한다.
1. 시간복잡도
시간복잡도란 어떤 알고리즘의 실행 속도가 대충 평균적으로 어느 정도 될지 가늠할 수 있는 척도이다. 표기에는 주로 빅-오 표기법(Big-O Notation)을 사용한다.
O(1)이라고 표기된 알고리즘의 속도는 실행 시 무조건 1만에 종료된다는 뜻이며, O(n)이라고 표기된 알고리즘의 속도는 n만에 종료된다는 뜻이다. 자료의 수가 1이면 1만에, 100이면 100만에 종료된다. O(logn)은 자료의 수가 2이면 log(2)=0.301029..., 10이면 log(10)=1만에 종료된다. 물론 데이터 처리에 1 미만이라는 것은 있을 수 없으므로 1 미만은 1로 간주할 수 있다(데이터 개수가 0이라면 0으로 간주할 수도 있겠다).
선형 그래프로 보면 시간복잡도에 따른 데이터 개수 당 속도 차이를 볼 수 있다. 가로 축(X축)은 데이터의 개수, 세로 축(Y축)은 데이터 개수에 따른 속도이다. O(1) ≤ O(logn) ＜ O(n) ＜ O(nlogn) ＜ O(n^2) ＜ O(2^n) ＜ O(n!) ＜ O(n^n) 순으로 느려지는 것을 확인할 수 있다.
2. 자료구조의 종류
자료구조로 일반적으로 대학교 강의나 전문서적에서 많이 볼 수 있는 것이라면 다음과 같은 종류가 있겠다.
| 배열 리스트 (Array List) | |
| 연결 리스트 (Linked List) | |
| 스택 (Stack) | |
| 큐 (Queue) | |
| 해시 테이블 (Hash Table) | |
| 이진 트리 (Binary Tree) | |
| 그래프 (Graph) | |
스택과 큐는 보통 배열 리스트와 연결 리스트 중 하나를 확장해서 구현하고, 해시 테이블은 내부적으로 배열 리스트가 쓰이는 편이다.
또한 연결 리스트는 단일 연결 리스트와 이중 연결 리스트가 존재하며, 결국에는 같은 원리로 되어있지만 이중 연결 리스트는 이전 노드로 돌아갈 수 있다는 차이가 있다.
이진 트리, 즉 트리는 그래프의 일종이고, 트리와 그래프 모두 배열과 연결 리스트 중 하나를 선택해서 구현할 수 있다. 그래프에 방향성이 없다면(순환이 가능하다면) 트리가 될 수 있다.
3. 자료구조 연산별 시간복잡도
그래프를 제외한 자료구조의 각 연산별 이론상 평균 시간복잡도는 대체로 다음과 같다.
| 자료구조 | 접근 | 검색 | 입력 | 삭제 |
|---|---|---|---|---|
| 배열 리스트 | O(1) | O(n) | O(n) | O(n) |
| 단일 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트 | O(n) | O(n) | O(1) | O(1) |
| 스택 | O(n) | O(n) | O(1) | O(1) |
| 큐 | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블 | 불가 | O(1) | O(1) | O(1) |
| 이진 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
그래프의 각 연산별 이론상 평균 시간복잡도는 대체로 다음과 같다. 여기서 V는 정점의 수, E는 간선의 수를 나타낸다.
| 그래프 종류 | 정점 추가 | 간선 추가 | 정점 제거 | 간선 제거 | 보관 | 질의 |
|---|---|---|---|---|---|---|
| 인접 리스트 | O(1) | O(1) | O(|V|+|E|) | O(|E|) | O(|V|+|E|) | O(|V|) |
| 범위 리스트 | O(1) | O(1) | O(|E|) | O(|E|) | O(|V|+|E|) | O(|E|) |
| 인접 행렬 | O(|V|^2) | O(1) | O(|V|^2) | O(1) | O(|V|^2) | O(1) |
| 범위 행렬 | O(|V|·|E|) | O(|V|·|E|) | O(|V|·|E|) | O(|V|·|E|) | O(|V|·|E|) | O(|E|) |
또한 배열 리스트의 정렬 알고리즘 당 시간복잡도는 다음과 같다. 공간복잡도(알고리즘 실행에 사용하는 메모리 공간의 크기)도 첨부.
| 정렬 알고리즘 | 최상 | 평균 | 최악 | 최악의 공간복잡도 |
|---|---|---|---|---|
| 퀵 정렬 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) |
| 병합 정렬 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) |
| 힙 정렬 | O(n) | O(nlogn) | O(nlogn) | O(n) |
| 버블 정렬 | O(n) | O(n^2) | O(n^2) | O(1) |
| 삽입 정렬 | O(n) | O(n^2) | O(n^2) | O(1) |
| 선택 정렬 | O(n^2) | O(n^2) | O(n^2) | O(1) |
퀵 정렬이 이름만큼 빠르냐면 생각보다 최악의 시간 복잡도를 생각하면 그렇지 않다는 것을 볼 수 있다. 그렇다고 병합 정렬이나 힙 정렬을 사용하기에는 공간복잡도를 봤을 때 병합 정렬이나 힙 정렬에 비해 퀵 정렬이 메모리 공간을 덜 쓴다는 것도 볼 수 있다.
시간복잡도에 대한 출처는 이곳. 더 자세한 내용은 이 출처에서 찾아볼 수 있다.
댈엄지님의 창작활동을 응원하고 싶으세요?
