BIG-O NOTATION · 속도의 단위
꺼내는 속도의 단위 — 빅쓰리만
O(1)
상수 시간
좌석 번호 알고 바로 앉기 — 데이터 수와 무관하게 항상 한 번에 접근
O(log n)
로그 시간
중간 페이지 펼쳐 절반 버리기 — 탐색할 때마다 범위가 반으로 줄어듦
O(n)
선형 시간
명단 처음부터 끝까지 — 데이터가 늘면 시간도 그만큼 늘어남
암기팁
Big-O 빅쓰리 —
O(1) 즉답 ·
O(log n) 반토막 ·
O(n) 한 바퀴
| 동작 |
배열 |
연결 리스트 |
스택 |
큐 |
| 접근 |
O(1) |
O(n) |
O(1) |
O(1) |
| 삽입 |
O(n) |
O(1) |
O(1) |
O(1) |
| 삭제 |
O(n) |
O(1) |
O(1) |
O(1) |
시험 한 줄
배열 인덱스 접근 = O(1), 연결 리스트 인덱스 접근 = O(n) — 이 한 줄이 단골 출제 포인트.
정렬·해시 분석은 다음 단원에서 이어집니다.