# [07-04] 최선/평균/최악 경우 분석
같은 알고리즘도 입력에 따라 성능이 달라지므로, 최선/평균/최악의 경우를 각각 분석하여 알고리즘의 전체적인 성능을 이해해야 합니다.
🎯 경우별 분석이란 무엇인가
왜 입력에 따라 성능이 다른가?
같은 알고리즘도 입력이 다르면 성능이 크게 달라집니다.
실생활 비유:
책에서 특정 페이지 찾기:
최선의 경우:
- 첫 페이지가 목표 페이지
- 1번 만에 찾음
평균적인 경우:
- 중간쯤에 있음
- 절반 정도 확인
최악의 경우:
- 마지막 페이지가 목표
- 전체를 다 확인프로그래밍 예시:
def linear_search(arr, target):
"""
선형 탐색
입력에 따라 성능이 다름!
"""
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
# 최선: arr = [5, 2, 8], target = 5
# → 첫 번째에 있음, 1번 비교
# 평균: arr = [1, 2, 3, 4, 5], target = 3
# → 중간에 있음, n/2번 비교
# 최악: arr = [1, 2, 3, 4, 5], target = 5
# → 마지막에 있음, n번 비교
# 또는 arr = [1, 2, 3], target = 10
# → 없음, n번 비교세 가지 경우의 정의
최선의 경우 (Best Case):
- 가장 유리한 입력
- 가장 빠른 실행
- Ω(g(n))으로 표현
평균의 경우 (Average Case):
- 전형적인 입력
- 기댓값 계산
- Θ(g(n))으로 표현 (많은 경우)
최악의 경우 (Worst Case):
- 가장 불리한 입력
- 가장 느린 실행
- O(g(n))으로 표현🎲 최선의 경우 분석
최선의 경우란?
최선의 경우(Best Case)는 알고리즘이 가장 빠르게 실행되는 입력 조건입니다.
특징:
장점:
- 이론적 하한 제시
- 최적화 가능성 파악
단점:
- 실무에서 거의 의미 없음
- 운이 좋아야 발생
- 성능 보장 안 됨
표현:
- Ω(g(n)) 사용최선의 경우 예시
예시 1: 선형 탐색
def linear_search(arr, target):
"""
최선: Ω(1)
첫 번째 원소가 target
"""
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
# 최선의 입력:
arr = [100, 2, 3, 4, 5]
target = 100
# → 1번 비교로 종료
# → Ω(1)예시 2: 삽입 정렬
def insertion_sort(arr):
"""
최선: Ω(n)
이미 정렬된 배열
"""
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
# 이미 정렬되어 있으면 while 진입 안 함
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# 최선의 입력:
arr = [1, 2, 3, 4, 5] # 이미 정렬됨
# → 각 i마다 1번 비교만
# → 총 n번 비교
# → Ω(n)예시 3: 퀵 정렬
def quick_sort(arr):
"""
최선: Ω(n log n)
피벗이 항상 중간값
"""
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# 최선의 입력:
# 피벗이 항상 정확히 중간에 위치
# → 균등 분할
# → Ω(n log n)📊 평균의 경우 분석
평균의 경우란?
평균의 경우(Average Case)는 모든 가능한 입력에 대한 성능의 기댓값입니다.
특징:
장점:
- 실제 성능 반영
- 실무에서 유용
단점:
- 계산이 어려움
- 입력 분포 가정 필요
표현:
- Θ(g(n)) 또는 O(g(n))평균 경우 계산 방법
확률적 분석 과정:
1. 가능한 모든 입력 나열
2. 각 입력의 확률 계산
3. 각 입력의 실행 시간 계산
4. 기댓값 계산
E[T(n)] = Σ P(입력_i) × T(입력_i)
여기서:
- E[T(n)]: 기댓값
- P(입력_i): 입력_i의 확률
- T(입력_i): 입력_i에서의 실행 시간평균 경우 예시
예시 1: 선형 탐색 (성공)
def linear_search(arr, target):
"""
평균 경우 분석
가정: target이 배열에 있음
각 위치에 있을 확률은 같음 (1/n)
"""
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
# 분석:
# n개 원소, target이 i번째에 있을 확률 = 1/n
# i번째에 있으면 i번 비교
# 기댓값:
# E[비교 횟수] = Σ(i=1 to n) (1/n) × i
# = (1/n) × [1 + 2 + 3 + ... + n]
# = (1/n) × n(n+1)/2
# = (n+1)/2
# ≈ n/2
# 평균: Θ(n)상세 계산:
배열: [a₁, a₂, a₃, ..., aₙ]
target이 각 위치에 있을 확률: 1/n
위치 비교 횟수 확률 기여도
--------------------------------------
1 1 1/n 1/n
2 2 1/n 2/n
3 3 1/n 3/n
...
n n 1/n n/n
총 기댓값:
E = (1 + 2 + 3 + ... + n) / n
= [n(n+1)/2] / n
= (n+1)/2
= n/2 + 1/2
≈ n/2 (n이 클 때)
∴ 평균: Θ(n)예시 2: 선형 탐색 (실패 포함)
# 더 현실적인 분석:
# target이 있을 확률 = p
# target이 없을 확률 = 1-p
# 있는 경우 평균: (n+1)/2번
# 없는 경우: n번
# 전체 평균:
# E = p × (n+1)/2 + (1-p) × n
# = p(n+1)/2 + n - pn
# = pn/2 + p/2 + n - pn
# = n - pn/2 + p/2
# = n(1 - p/2) + p/2
# p = 0.5 (50% 확률로 있음):
# E = n(1 - 0.25) + 0.25
# = 0.75n + 0.25
# ≈ 3n/4
# 여전히 Θ(n)예시 3: 퀵 정렬
def quick_sort_average():
"""
평균 경우: Θ(n log n)
가정: 피벗이 무작위 선택
모든 순열이 동일 확률
분석:
T(n) = T(k) + T(n-k-1) + Θ(n)
k: 피벗의 순위 (0부터 n-1까지 균등)
평균:
E[T(n)] = E[T(k) + T(n-k-1)] + Θ(n)
= (1/n) Σ(k=0 to n-1) [T(k) + T(n-k-1)] + Θ(n)
이를 풀면:
E[T(n)] = Θ(n log n)
"""
pass
# 직관적 이해:
# - 피벗이 평균적으로 "중간쯤" 선택됨
# - 균형 잡힌 분할 → log n 레벨
# - 각 레벨 O(n) 작업
# → 총 Θ(n log n)💥 최악의 경우 분석
최악의 경우란?
최악의 경우(Worst Case)는 알고리즘이 가장 느리게 실행되는 입력 조건입니다.
특징:
장점:
- 성능 보장 제공
- 안전한 설계 가능
- 가장 중요!
단점:
- 실제보다 비관적일 수 있음
표현:
- O(g(n)) 사용왜 최악의 경우가 중요한가?
실무에서 최악의 경우를 고려해야 하는 이유:
1. 성능 보장:
"절대 n² 시간을 넘지 않습니다"
→ 신뢰성
2. 최악이 자주 발생:
정렬된 데이터에 삽입 정렬
→ 매번 최악!
3. 안전 중요 시스템:
의료 기기, 항공
→ 최악도 허용 범위 내
4. 실시간 시스템:
게임, 동영상
→ 최대 지연 시간 보장최악의 경우 예시
예시 1: 선형 탐색
def linear_search(arr, target):
"""
최악: O(n)
1) target이 마지막에 있음
2) target이 없음
"""
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
# 최악의 입력 1:
arr = [1, 2, 3, 4, 5]
target = 5
# → n번 비교
# 최악의 입력 2:
arr = [1, 2, 3, 4, 5]
target = 10 # 없음
# → n번 비교
# 최악: O(n)예시 2: 버블 정렬
def bubble_sort(arr):
"""
최악: O(n²)
역순 정렬된 배열
"""
n = len(arr)
for i in range(n - 1):
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# 최악의 입력:
arr = [5, 4, 3, 2, 1] # 역순
# → 모든 쌍을 교환
# → n(n-1)/2번 교환
# → O(n²)예시 3: 퀵 정렬
def quick_sort_worst(arr):
"""
최악: O(n²)
피벗이 항상 최솟값 또는 최댓값
"""
if len(arr) <= 1:
return arr
# 나쁜 피벗 선택: 항상 첫 원소
pivot = arr[0]
left = [x for x in arr[1:] if x < pivot]
middle = [pivot]
right = [x for x in arr[1:] if x >= pivot]
return quick_sort_worst(left) + middle + quick_sort_worst(right)
# 최악의 입력:
arr = [1, 2, 3, 4, 5] # 이미 정렬됨
# 피벗이 항상 최솟값
# → 불균형 분할
# → n + (n-1) + (n-2) + ... + 1
# → O(n²)
# 해결: 무작위 피벗 또는 중간값 선택📈 알고리즘별 경우 분석
정렬 알고리즘 비교
알고리즘 최선 평균 최악
--------------------------------------------------
버블 정렬 O(n) O(n²) O(n²)
선택 정렬 O(n²) O(n²) O(n²)
삽입 정렬 O(n) O(n²) O(n²)
병합 정렬 Θ(n log n) Θ(n log n) Θ(n log n)
퀵 정렬 Ω(n log n) Θ(n log n) O(n²)
힙 정렬 Ω(n log n) Θ(n log n) O(n log n)분석:
# 버블 정렬
def bubble_sort(arr):
"""
최선: O(n) - 이미 정렬됨 (최적화 버전)
평균: O(n²)
최악: O(n²) - 역순
"""
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # 최선의 경우 조기 종료
break
# 삽입 정렬
def insertion_sort(arr):
"""
최선: O(n) - 이미 정렬됨
평균: O(n²)
최악: O(n²) - 역순
특징: 거의 정렬된 데이터에 매우 빠름!
"""
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
# 이미 정렬되어 있으면 while 안 들어감
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# 병합 정렬
def merge_sort(arr):
"""
최선: Θ(n log n)
평균: Θ(n log n)
최악: Θ(n log n)
특징: 항상 일정! 안정적!
"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
# 입력과 무관하게 항상 같은 분할탐색 알고리즘 비교
알고리즘 최선 평균 최악
--------------------------------------------------
선형 탐색 O(1) O(n) O(n)
이진 탐색 O(1) O(log n) O(log n)
해시 탐색 O(1) O(1) O(n)분석:
# 이진 탐색
def binary_search(arr, target):
"""
최선: O(1) - 중간에 있음
평균: O(log n)
최악: O(log n) - 없음
전제: 정렬된 배열
"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid # 최선: 첫 비교에 찾음
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # 최악: log n번 비교 후 실패
# 해시 테이블
class HashTable:
"""
최선: O(1) - 충돌 없음
평균: O(1) - 충돌 적음
최악: O(n) - 모든 원소가 같은 버킷
최악의 경우:
- 나쁜 해시 함수
- 모든 키가 같은 인덱스로
"""
pass🎯 실무 의사결정
어떤 경우를 고려해야 하는가?
시나리오별 선택:
1. 성능 보장 중요 (실시간, 안전) → 최악의 경우 최우선
예: 병합 정렬 (Θ(n log n) 보장)
2. 일반적인 웹 서비스 → 평균 경우 중요
예: 퀵 정렬 (평균 빠름)
3. 특수한 입력 패턴 → 최선의 경우 활용
예: 거의 정렬된 데이터 → 삽입 정렬하이브리드 접근
def tim_sort_strategy(arr):
"""
Python의 기본 정렬 (Timsort)
전략: 입력에 따라 다른 알고리즘
"""
n = len(arr)
# 작은 배열: 삽입 정렬
if n < 64:
return insertion_sort(arr)
# 큰 배열: 병합 정렬
# 단, 거의 정렬된 부분은 삽입 정렬
return adaptive_merge_sort(arr)
def intro_sort_strategy(arr):
"""
C++ STL sort (Introsort)
전략: 퀵 정렬 + 힙 정렬
"""
# 일반: 퀵 정렬 (평균 빠름)
# 재귀 깊이 초과 시: 힙 정렬 (최악 회피)
max_depth = 2 * log(len(arr))
return adaptive_quick_sort(arr, max_depth)실무 예시
예시 1: 데이터베이스 인덱스
선택: B-Tree vs 해시 인덱스
B-Tree:
- 최악: O(log n)
- 범위 검색 가능
- 안정적
해시:
- 평균: O(1)
- 최악: O(n) (충돌 시)
- 범위 검색 불가
결정:
→ 범위 검색 필요 → B-Tree
→ 단일 키 검색만 → 해시예시 2: 웹 서버 응답 시간
요구사항:
- 평균 응답 시간: 100ms 이하
- 최대 응답 시간: 1000ms 이하
선택:
평균이 중요하지만
최악도 허용 범위 내여야 함
→ 최악의 경우도 반드시 확인!💡 실무 팁
최악의 경우 회피
# 나쁜 예: 퀵 정렬 (피벗 고정)
def quick_sort_bad(arr):
if len(arr) <= 1:
return arr
pivot = arr[0] # 항상 첫 원소
# 정렬된 배열에서 O(n²)!
# ...
# 좋은 예: 무작위 피벗
import random
def quick_sort_good(arr):
if len(arr) <= 1:
return arr
# 무작위 피벗 선택
pivot_idx = random.randint(0, len(arr) - 1)
pivot = arr[pivot_idx]
# 최악의 경우 확률적으로 회피
# 평균 O(n log n) 보장입력 검증
def process_data(data):
"""
최악의 입력 패턴 사전 차단
"""
# 1. 크기 제한
if len(data) > MAX_SIZE:
raise ValueError("입력이 너무 큼")
# 2. 패턴 감지
if is_adversarial_input(data):
# 다른 알고리즘 사용
return robust_algorithm(data)
# 3. 일반 알고리즘
return fast_algorithm(data)성능 모니터링
import time
def monitored_sort(arr):
"""
실행 시간 측정
"""
start = time.time()
result = sort_algorithm(arr)
elapsed = time.time() - start
# 경고: 최악의 경우 감지
if elapsed > THRESHOLD:
log_warning(f"느린 정렬: {elapsed}초, 크기: {len(arr)}")
return result🎯 핵심 정리
세 가지 경우
최선의 경우:
- 가장 유리한 입력
- 이론적 하한
- Ω(g(n))
평균의 경우:
- 전형적인 입력
- 기댓값 계산
- 실무 중요
최악의 경우:
- 가장 불리한 입력
- 성능 보장
- 가장 중요!알고리즘 선택 기준
정렬 선택:
작은 배열 (< 50): 삽입 정렬
거의 정렬된 경우: 삽입 정렬
성능 보장 필요: 병합 정렬
평균적으로 빠르게: 퀵 정렬복잡도 표현
최선: Ω(g(n)) 또는 Θ(g(n))
평균: Θ(g(n)) 또는 O(g(n))
최악: O(g(n))
보통 최악으로 표현:
"이 알고리즘은 O(n log n)입니다"
= "최악의 경우 O(n log n)"실무 지침
성능 중요 시스템:
→ 최악의 경우 우선
→ 병합 정렬, 힙 정렬
일반 시스템:
→ 평균의 경우 고려
→ 퀵 정렬, 해시
특수 상황:
→ 입력 특성 활용
→ 삽입 정렬 (거의 정렬됨)🔗 다음 글에서는
[07-05] 상수 계수와 실제 성능
- 이론 vs 실제: Big-O로는 알 수 없는 실제 성능 차이
- 상수 계수의 영향: 같은 O(n)도 10배 차이 가능
- 캐시와 메모리: 하드웨어가 성능에 미치는 영향
- 실무 벤치마크: 실제 측정과 프로파일링 방법
이전 글: [07-03] 점근적 표기법
다음 글: [07-05] 상수 계수와 실제 성능
시리즈: P1. Computer Science
AI 전문가를 꿈꾸는 도전자