자료구조는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 말한다.
5.1 복잡도
5.1.1 시간 복잡도
- 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계이다.
- 어떠한 알고리즘의 로직이 얼마나 오랜 시간이 걸리는지를 나타내는 데 쓰인다.
- 빅오 표기법으로 나타낸다.
- 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는 지 나타내는 것이다.
- 효율적인 코드로 개선하는 데 쓰이는 척도가 된다.
5.1.2 공간 복잡도
- 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말한다.
- 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함된다.
5.1.3 자료 구조에서의 시간 복잡도
자료구조를 쓸 때는 이러한 시간 복잡도를 잘 생각해야 한다.
< 자료 구조의 평균 시간 복잡도 >
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열(array) | O(1) | O(n) | O(n) | O(n) |
| 스택(stack) | O(n) | O(n) | O(1) | O(1) |
| 큐(queue) | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트(doubly linked list | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블(hash table | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리(BST) | O(logn) | O(logn) | O(logn) | O(logn) |
| AVL 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
| 레드 블랙 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
< 자료 구조 최악의 시간 복잡도 >
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열(array) | O(1) | O(n) | O(n) | O(n) |
| 스택(stack) | O(n) | O(n) | O(1) | O(1) |
| 큐(queue) | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트(doubly linked list | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블(hash table | O(n) | O(n) | O(n) | O(n) |
| 이진 탐색 트리(BST) | O(n) | O(n) | O(n) | O(n) |
| AVL 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
| 레드 블랙 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
