Big-O Reading
복잡도는 반복 구조가 커지는 모양으로 읽는다
입력 N이 커질 때 반복 횟수, 재귀 깊이, 추가 메모리가 어떤 계단으로 올라가는지 먼저 표시한다.
통과
주의
대표 성장 계단
O(1)입력과 무관
O(log N)절반씩 축소
O(N)한 번 훑기
O(N log N)정렬, 분할 정복
O(N²)모든 쌍 비교
| 코드 구조 | 비용 신호 | 오판 방지 |
|---|---|---|
| 한 번 순회 | 각 원소를 한 번씩 본다 → O(N) | 반복문이 두 개여도 독립이면 O(2N) = O(N) |
| 중첩 반복 | 각 원소마다 다시 전체를 본다 → O(N²) | 안쪽 범위가 줄어도 대개 삼각합으로 O(N²) |
| 절반 축소 | 탐색 공간이 반으로 줄어든다 → O(log N) | 배열이 정렬되지 않으면 비용보다 정답성이 먼저 깨짐 |
| 추가 저장 | 원본 외 배열, 해시, 스택 크기를 따로 센다 | 입력 배열 자체는 추가 공간이 아니다 |