시간 복잡도 O(1), O(log n) - "빠르다"의 기준
데이터가 아무리 많아져도 걸리는 시간이 늘어나지 않는지를 나타내는 표기입니다.
| 표기 | 의미 | 비유 |
|---|---|---|
| O(1) | 데이터 개수와 무관하게 즉시 | 번호표를 보고 바로 해당 사물함 열기 |
| O(n) | 데이터 수에 비례해서 느려짐 | 1번 상자부터 끝까지 하나씩 열어보기 |
| O(log n) | 데이터가 100배 늘어도 단계 몇 개만 추가 | 절반씩 줄여가며 찾기 |
요구사항에서 "삽입/삭제/이동은 O(1)"라고 한 이유: LRU 추적은 매 명령마다 일어나므로 즉각적이어야 하기 때문입니다.
출처: Codyssey-B1/B5-1