Big-O, Big-Θ, Big-Ω, 그리고 최선/평균/최악

"서로 다른 두 질문이 자꾸 섞여. '내 경계가 얼마나 빡빡해?' 와 '어떤 입력을 분석하는 거야?' 별개의 축이야. 풀어놓으면 혼란의 절반이 걷혀."

축 하나: 경계가 얼마나 빡빡한가

O, Θ, Ω 는 한 함수의 성장을 묶는 세 가지 방법이야.

Big-O 는 위쪽 경계야. "기껏해야 이만큼 빨리 커진다." 어떤 알고리즘이 O(n²)이라는 건 제곱보다 나쁘진 않다는 약속이지, 더 좋을 수도 있어.
Big-Ω (오메가) 는 아래쪽 경계야. "적어도 이만큼 빨리 커진다." 바닥이지.
Big-Θ (세타) 는 빡빡한 경계야. 위아래가 일치해서 진짜 모양을 짚은 거고. Θ(n)은 "정확히 n처럼 커진다, 빠져나갈 구멍 없음"이야.

일상 대화에서는 다들 "O(n)"이라고 말하면서 사실은 정확한 증가율인 Θ(n)을 뜻해. 보통은 괜찮아. 다만 엄밀히 따지면 O는 천장일 뿐이라는 걸 알아둬. 누가 네 "O"를 "Θ"로 깐깐하게 고치면 지금 이 얘기를 하는 거야.

축 둘: 어떤 입력인가

이건 완전히 다른 축이고, 앞의 축이랑 섞는 게 입문자의 대표적인 실수야. 최선/평균/최악은 이걸 물어. 입력 크기가 같을 때, 그 입력이 어떻게 배치돼 있는 경우를 보는 거야?

최선 케이스 — 제일 운 좋은 입력. 선형 탐색이 0번 위치에서 찾으면 O(1). 굳이 매달릴 숫자는 아니야.
최악 케이스 — 제일 운 나쁜 입력. 선형 탐색이 끝까지 훑고 못 찾으면 O(n). 보통 이게 중요한 숫자야. 보장이니까.
평균 케이스 — 현실적인 데이터로 평균 낸 전형적인 입력. 선형 탐색이면 대략 n/2이고, 여전히 O(n)이야.

그래서 퀵소트는 "평균 Θ(n log n), 최악 Θ(n²)"이야. 다른 두 입력, 다른 두 모양, 둘 다 참이지. 해시 조회도 "평균 O(1), 최악 O(n)"이고. 모순이 아니라 다른 입력에 이름을 붙인 거야.

O/Θ/Ω 는 한 함수의 성장을 묶어. 천장, 정확, 바닥. 최선/평균/최악은 어떤 입력을 분석할지 고르는 거고. 다른 축이니까 합치지 마. 설계는 최악에 맞추고, 기대는 평균에 걸어.

어떤 숫자가 결정을 지배해야 하나

보통 둘이야. 최악 케이스는 사용자가 뭘 던지든 지킬 수 있는 약속이고, 평균 케이스는 실제로 대부분 일어나는 일이야. 최선 케이스는 거의 자랑에 가까워. "답이 우연히 첫 번째면 O(1)"은 쓸모 있는 걸 하나도 안 알려주거든. 시스템이 단단한 보장을 요구하면 (실시간, 안전 필수) 최악이 왕이고, 실전에서 빠르기만 하면 되는 경우엔 평균이 설계를 이끄는 일이 많아.

피파의 고백

한번은 평균 케이스 O(1)만 믿고 출시했다가 최악이 O(n)이라는 걸 까맣게 잊었어. 그러다 사용자가 딱 그 병적인 입력을 먹였지. 모든 키가 충돌하는 입력. "즉시"가 "멈춤"이 됐어. 평균 케이스는 내가 바라는 거고, 최악 케이스는 내가 책임지는 거야. 이젠 아빠가 던질 후속 질문을 내가 먼저 던져. "그리고 적이 이걸로 할 수 있는 최악은 뭐야?"

Code

최선, 최악, 평균, 같은 코드·python

# 한 알고리즘, 세 입력: 최선, 최악, 평균 케이스.

def linear_search(items, target):
    """(찾음 여부, 비교 횟수) 반환."""
    for i, x in enumerate(items):
        if x == target:
            return True, i + 1        # 사용한 비교 횟수
    return False, len(items)

data = list(range(1000))

# 최선: target 이 첫 번째 -> 비교 1번 -> O(1)
print("best :", linear_search(data, 0)[1])

# 최악: target 없음 -> 전부 훑음 -> O(n)
print("worst:", linear_search(data, -1)[1])

# 평균: target 이 중간 어딘가 -> ~n/2 -> 여전히 O(n)
print("avg  :", linear_search(data, 500)[1])

# 같은 코드, 같은 n. *입력* 이 최선/최악/평균을 골라.
# 여기서 최악 케이스의 빅오는 O(n). 최선은 O(1).

Exercise

각각의 최선, 최악, 평균 케이스 복잡도를 대봐. (1) 선형 훑기로 리스트가 값을 담고 있는지 확인, (2) 파이썬 리스트 앞에 삽입, (3) 해시맵에서 키 찾기. 그다음 절대 멈추면 안 되는 시스템이라면 어느 케이스를 기준으로 설계할지 말해봐.

Hint

리스트 앞 삽입은 늘 O(n)이야. 모든 케이스가 같아. 전부 밀어야 하니까. 해시 조회는 평균 O(1)인데 최악이 O(n)이고, 절대 안 멈춰야 하는 시스템은 그 최악을 존중해야 해.

축 하나: 경계가 얼마나 빡빡한가

축 둘: 어떤 입력인가

어떤 숫자가 결정을 지배해야 하나

피파의 고백

Code

External links

Exercise

Progress

댓글 0