complexity map

반복문 신호를 보면 시간 복잡도가 좁혀진다

반복문 개수만 세지 말고 각 반복 범위가 독립인지 줄어드는지부터 본다.

한 번 훑기O(N)

입력 크기만큼 한 번 돈다.

중첩 반복O(N²)

각 i마다 j가 다시 돈다.

반씩 줄어듦O(log N)

탐색 범위가 계속 줄어든다.

구분의미판단
정렬 후 선형O(N log N)정렬 비용이 지배
입력 두 개O(NM)N과 M이 독립이면 곱
주의반복문 개수보다 범위줄어드는 반복은 다르게 본다.

핵심 반복문 개수만 세지 말고 각 반복 범위가 독립인지 줄어드는지부터 본다.