복잡도를 반복문에서 바로 읽어내기

"빅오 읽기의 90% 는 반복문 읽기야. 순차 반복문은 더해. 중첩 반복문은 곱해. 나머지는 거의 다 각주야."

무거운 일을 다 하는 두 규칙

알고리즘의 복잡도를 찾는 데 미적분은 필요 없어. 반복문을 찾아서 두 규칙을 적용하면 돼:

순차 반복문은 더해. n 을 도는 반복문, 그다음 또 n 을 도는 반복문은 n + n = 2n = O(n). 하나 끝나고 하나, 그래서 더하고 — 상수는 버려.
중첩 반복문은 곱해. n 을 도는 반복문 안에 또 n 을 도는 게 있으면 n × n = O(n²). 세 겹이면 O(n³). 안쪽은 곱해.

그래서 게임 전체가 이거야: 가장 깊은 중첩을 찾아, 제일 많이 곱해진 항이 지배하니까. 삼중 중첩 반복문 하나랑 따로 떨어진 단일 반복문 쉰 개를 가진 함수는 O(n³) 이야 — 단일 반복문들은 세제곱 옆에서 잡음이야.

log n 의 반전

패턴을 깨는 반복문 모양 하나는 외워둘 가치가 있어: 매 단계 남은 일을 절반으로 자르는 반복문은 O(n) 이 아니라 O(log n) 이야. n 에서 시작해 n/2, n/4, n/8 … 로 반 잘라 가면 약 log₂(n) 단계에 1 에 도달해. 십억 개면 겨우 30 단계. 이게 이진 탐색이랑 균형 트리 뒤의 비밀이고, 처음 보면 "log n" 이 사기처럼 느껴지는 이유야.

복잡도를 읽으려면: 반복문을 찾아. 순차 반복문은 더하고 (제일 큰 것만 남겨). 중첩 반복문은 곱하고 (깊이를 세). 반 자르는 반복문은 log n. 네가 분석할 코드 대부분이 여기에 들어가.

함정: 숨은 반복문

제일 치명적인 O(n²) 은 단일 반복문처럼 보이는 코드에 숨어. 반복문 안에 if x in my_list 를 쓰면, 반복문을 중첩한 거야 — in 이 리스트에선 몰래 리스트 전체를 훑거든. 보이는 반복문 하나, 안 보이는 반복문 하나, 총 n². 같은 함정이 반복문 안 슬라이싱, 반복문 안 += 로 문자열 짓기, list.insert(0, ...) 반복 호출에도 숨어. 네가 호출하는 연산의 비용을 아는 게 복잡도 분석의 절반이야 — 아래 Python wiki 링크는 북마크할 가치 있어.

피파의 고백

한 번은 함수를 깔끔한 단일 반복문으로 "최적화" 하고 자랑스럽게 O(n) 이라고 불렀어. 아빠가 한 줄을 가리켰어: if item in seen_list. 그 순진한 in 이 매 반복마다 커지는 리스트를 훑고 있었어 — 내 예쁜 단일 반복문은 조용히 O(n²) 이었던 거야. seen_list 를 set 으로 바꾸니 진짜 O(n) 이 됐어. 네가 볼 수 있는 반복문이 늘 네가 가진 반복문은 아니야.

Code

함수 여섯, 복잡도 여섯·python

# 각각의 복잡도를 읽어. 답은 반복문 구조에 있어.

def a(items):                       # O(n): 반복문 하나
    for x in items:
        print(x)

def b(items):                       # O(n): 순차 반복문 둘 -> n + n
    for x in items: print(x)
    for x in items: print(x)

def c(items):                       # O(n^2): 중첩 반복문 -> n * n
    for x in items:
        for y in items:
            print(x, y)

def d(items):                       # O(log n): 매 단계 일이 절반
    n = len(items)
    while n > 1:
        n = n // 2
        print(n)

def trap(items):                    # O(n) 처럼 보이지만, 사실 O(n^2)!
    seen = []
    for x in items:
        if x in seen:               # 리스트의 'in' = 숨은 안쪽 훑기
            continue
        seen.append(x)

def trap_fixed(items):              # O(n): set 멤버십은 O(1)
    seen = set()
    for x in items:
        if x in seen:               # set 의 'in' = 숨은 반복문 없음
            continue
        seen.add(x)

Exercise

손으로 분석해봐: 한 함수가 n 개 항목 리스트를 돌고, 각 항목마다 같은 리스트에 .index() 조회 (값을 찾으려 훑음) 를 하고, 결과에 추가해. 진짜 복잡도가 뭐고, 어느 줄이 숨은 반복문이야? 어떻게 O(n) 으로 만들어?

Hint

.index() 가 리스트를 훑어 — 그게 네 보이는 O(n) 반복문 안의 안쪽 O(n) 이야. 값→위치 dict 를 앞에서 한 번 만들면 숨은 훑기를 죽여.

무거운 일을 다 하는 두 규칙

log n 의 반전

함정: 숨은 반복문

피파의 고백

Code

External links

Exercise

Progress

댓글 0