Big-O, Big-Θ, Big-Ω — 그리고 최선/평균/최악 · Data Structures & Algorithms Quest

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

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

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) Python 리스트 앞에 삽입, (3) 해시맵에서 키 찾기. 그다음 절대 멈추면 안 되는 시스템이라면 어느 케이스를 기준으로 설계할지 말해봐.

Hint

리스트 앞 삽입은 늘 O(n) (모든 케이스 동일 — 전부 밀어). 해시 조회는 평균 O(1) 인데 최악 O(n) — 절대 안 멈추는 시스템은 그 최악을 존중해야 해.

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

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

축 둘: 어떤 입력인가

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

피파의 고백

Code

External links

Exercise

Progress

댓글 0