알고리즘 공부를 하기 위해 코테를 풀다보니 List와 Set의 시간복잡도 차이에 놓치고 있는 부분이 생겼다.
List vs Set 시간 복잡도
| 기능 | List | Set |
| 추가 (Add) | O(1) | O(1) |
| 제거 (Remove) | O(n) | O(1) |
| 탐색 (Serch) | O(n) | O(1) |
| 정렬 (Sort) | O(n logn) | - |
여기서 내가 놓친 것은 "remove"이다. List는 순서가 있는 자료구조이고, Set는 순서가 없는 자료구조이다. 그렇기 때문에 List에서 제거를 할때는 탐색을 통해 해당 값을 찾고, 제거한다. 하지만 Set은 내부적으로 해시 테이블의 구조로 이루어져있다. 그래서 제거하는데 시간복잡도가 O(1)이 걸린다.
Set이 해시 테이블 기반으로 구현되어있다고?
set에 대해 조금 더 자세히 살펴보기 위해 해시 테이블을 생각해보자. 해시테이블은 key와 value 쌍으로 이루어져있다. 즉, (key, value)로 구성되어 있는 것이다. 보통 파이썬에서는 딕셔너리가 해시 테이블의 구현체인데 코드로 살펴보면 다음과 같다.
dict = { 1: "one", 2: "two"}
print(dict[1]) # one
여기서 1은 key가 되는 것이고, one은 value가 되는 것이다. 그리고 key는 중복될 수 없다. 따라서 key를 이용해 value를 찾을 때는 시간복잡도가 O(1) 이다. 여기서도 set과 똑같이 데이터에 순서는 없다.
🙌 그렇다면 Set은??
Set은 해시 테이블을 기반으로 동작하지만 차이가 있다. key는 있고 value는 없다. 찾아보니 set에 데이터를 저장할 때, 각 요소를 key로 사용한다고 한다. 그렇기 때문에 중복을 허용하지 않는 것이다.
몰랐던 부분을 많이 공부하고 간다ㅎㅎ!
'📚 CS > 알고리즘, 자료구조' 카테고리의 다른 글
| [알고리즘] 공간 복잡도 계산 (1) | 2025.03.05 |
|---|---|
| [알고리즘] 다익스트라(Dijkstra) 알고리즘 (0) | 2024.12.01 |
| [알고리즘] 코드로 알아보는 DFS 알고리즘 (0) | 2024.11.07 |
| [알고리즘] 삽입 정렬 (insertion sort) 이란? (1) | 2024.10.05 |
| [알고리즘] 선택 정렬 (selection sort) 이란? (1) | 2024.10.01 |