자료구조의 시간복잡도는 해당 자료구조에 대한 삽입, 삭제, 검색 등의 연산을 수행할 때 걸리는 시간을 나타내는 지표입니다. 시간복잡도는 보통 'O(연산 횟수)'로 표현되며, 연산 횟수가 적을수록 해당 자료구조의 성능이 더 우수합니다.
-
해시 테이블: 삽입, 삭제, 검색 모두 O(1)이기 때문에, 매우 빠른 검색 속도를 가집니다. 하지만 충돌이 발생할 경우에는 다른 처리가 필요합니다.
-
힙: 삽입, 삭제 모두 O(log n)이며, 최대/최소 검색은 O(1)입니다. 일반적으로 우선순위 큐에서 사용됩니다.
-
AVL 트리: 삽입, 삭제, 검색 모두 O(log n)입니다. 균형을 유지하기 위해 회전 연산을 수행해야 하므로, 구현이 복잡합니다.
-
레드블랙 트리: 삽입, 삭제, 검색 모두 O(log n)입니다. AVL 트리보다 구현이 간단하며, 일반적으로 데이터베이스와 파일 시스템에서 사용됩니다.
-
스택: 삽입, 삭제, 검색 모두 O(1)입니다. 후입선출(LIFO) 방식으로 동작하며, 함수 호출 스택 등에 사용됩니다.
-
큐: 삽입, 삭제, 검색 모두 O(1)입니다. 선입선출(FIFO) 방식으로 동작하며, 대기열 등에 사용됩니다
-
연결 리스트: 삽입, 삭제는 O(1)이며, 검색은 O(n)입니다. 메모리를 동적으로 할당하기 때문에, 배열보다 더 유연한 자료구조입니다.
-
배열: 삽입, 삭제는 O(n)이며, 검색은 O(1)입니다. 메모리를 연속적으로 할당하기 때문에, 인덱스를 통한 검색이 빠릅니다. 크기를 변경할 때는 새로운 배열을 할당하고 이전 데이터를 복사해야 하므로, 비용이 큽니다.
시간복잡도에 따른 빠른 순서
| 자료구조 | 삽입 | 삭제 | 검색 |
|---|---|---|---|
| 해시 테이블 | O(1) | O(1) | O(1) |
| 스택 | O(1) | O(1) | O(1) |
| 큐 | O(1) | O(1) | O(1) |
| 힙 | O(log n) | O(log n) | O(1) |
| AVL 트리 | O(log n) | O(log n) | O(log n) |
| 레드블랙 트리 | O(log n) | O(log n) | O(log n) |
| 연결 리스트 | O(1) | O(1) | O(n) |
| 배열 | O(n) | O(n) | O(1) |
위 표는 각 자료구조의 삽입, 삭제, 검색 연산의 시간복잡도를 나타낸 것입니다. 연산 횟수가 적을수록 해당 자료구조의 성능이 더 우수합니다.
자료구조의 빠른 순서:
-
해시 테이블: 삽입, 삭제, 검색 모두 O(1)
-
스택: 삽입, 삭제, 검색 모두 O(1)
-
큐: 삽입, 삭제, 검색 모두 O(1)
-
힙: 삽입, 삭제 모두 O(log n), 최대/최소 검색은 O(1)
-
AVL 트리: 삽입, 삭제, 검색 모두 O(log n)
-
레드블랙 트리: 삽입, 삭제, 검색 모두 O(log n)
-
연결 리스트: 삽입, 삭제는 O(1), 검색은 O(n)
-
배열: 삽입, 삭제는 O(n), 검색은 O(1)
