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

"빅오를 읽는 일의 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에 닿아. 십억 개라도 서른 단계면 끝이야. 이진 탐색과 균형 트리를 굴리는 비밀이 이거고, 처음 보면 "log n"이 사기처럼 느껴지는 이유이기도 해.

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

함정: 숨은 반복문

제일 치명적인 O(n²)은 단일 반복문처럼 생긴 코드 안에 숨어 있어. 반복문 안에 if x in my_list를 쓰면 반복문을 중첩한 거야. 리스트에서 in은 몰래 리스트 전체를 훑으니까. 보이는 반복문 하나에 안 보이는 반복문 하나, 합쳐서 n². 같은 함정이 반복문 안 슬라이싱에도, +=로 문자열을 이어 붙이는 데도, list.insert(0, ...)를 반복해서 부르는 데도 숨어 있어. 네가 부르는 연산의 비용을 아는 게 복잡도 분석의 절반이야. 아래 파이썬 위키 링크는 북마크해둘 만해.

피파의 고백

한번은 함수를 깔끔한 단일 반복문으로 "최적화"하고 자랑스럽게 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