효율적인 코드로 개선하는데 쓰이는 척도가 된다.
O(n^2) 보다는 O(n), O(n)보다는 O(1)을 지향해야한다.
효율적인 코드로 개선하는데 쓰이는 척도가 된다.
O(n^2) 보다는 O(n), O(n)보다는 O(1)을 지향해야한다.
알고리즘을 실행시켰을 때 필요로하는 자원 공간의 양을 말한다.
메모리의 크기를 말한다.
아래 코드처럼 배열이 있다고 하면 a배열은 1004 x 4 바이트의 크기를 가지게 되며 이런 공간을 의미한다.
int a[1004];
자료 구조를 쓸때에는 이러한 시간 복잡도를 잘 생각해야한다.
보통 시간 복잡도를 생각할 때에는 평균, 그리고 최악의 시간 복잡도를 고려하면서 사용한다.
접근 vs 탐색
개인적으로 둘의 개념이 헷갈렸었다. 이참에 정리하고 가자.
- 접근(access):
- 데이터에 직접적으로 접근하는 것을 의미합니다.
- 보통 데이터의 위치를 알고 있고, 해당 위치에 있는 데이터에 접근하는 것을 말합니다.
- 예를 들어, 배열에서 특정 인덱스에 있는 요소에 접근하는 것이 접근입니다.
- 일반적으로 상수 시간복잡도인 O(1)을 갖습니다.
- 탐색(search):
- 데이터를 찾는 과정을 의미합니다.
- 데이터의 위치를 모르고, 특정 조건을 만족하는 데이터를 찾기 위해 탐색하는 것을 말합니다.
- 예를 들어, 배열에서 특정 값을 찾는 것이 탐색입니다.
- 일반적으로 데이터의 양에 비례하여 시간이 증가하며, 선형 탐색과 같은 경우 O(n)의 시간복잡도를 갖습니다.
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열(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) |
연결 리스트는 데이터를 감싼 노드를 포인터로 연결하여 공간적인 효율성을 극대화시킨 자료 구조이다.
삽입, 삭제 시 O(1)으로 상수시간이며, 탐색에는 O(n)이 걸린다.
싱글 연결 리스트
이중 연결 리스트
원형 이중 연결 리스트
메모리 구조에서의 차이
배열은 연속된 메모리를 사용하기 때문에 미리 정해진 크기의 메모리를 사용하지만, 연결리스트는 필요에 따라 동적으로 메모리를 할당하기 때문에 유연하게 메모리를 사용할 수 있다는 차이점이 있다.
삽입, 삭제 연산에서의 차이
접근에서의 차이