알고리즘Easy#30
빅오 표기법(Big-O Notation)이란 무엇이며 왜 중요한가요?
#알고리즘#복잡도#Big-O
힌트
알고리즘의 효율성을 입력 크기에 따라 표현하는 방법입니다.
정답 및 해설
빅오 표기법(Big-O Notation)이란 무엇이며 왜 중요한가요?
빅오 표기법은 알고리즘의 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)를 입력 크기 n에 대한 함수로 표현하는 표기법입니다. 최악의 경우(Worst Case)를 기준으로 하며, 상수항과 계수를 무시하고 가장 지배적인 항만 남깁니다. 알고리즘의 효율성을 객관적으로 비교하고, 대규모 데이터에서의 성능을 예측하는 데 필수적인 도구입니다.
빅오 표기법의 정의
수학적 정의
f(n) = O(g(n))이면:
어떤 양의 상수 c와 n₀가 존재하여
n ≥ n₀인 모든 n에 대해 f(n) ≤ c × g(n)
즉, f(n)의 성장률이 g(n)보다 빠르지 않음을 의미
핵심 원칙
- 상수 무시:
5n→O(n),100→O(1) - 낮은 차수 항 무시:
n² + n→O(n²) - 최악의 경우 기준: 입력이 가장 불리할 때의 성능
# 예시: 아래 함수의 빅오 표기
def example(n):
result = 0 # O(1)
for i in range(n): # O(n)
result += i # O(1)
return result # O(1)
# 총 실행 횟수: 1 + n × 1 + 1 = n + 2
# 빅오: O(n + 2) → O(n) (상수항 무시)
주요 시간 복잡도 분류
O(1) - 상수 시간
입력 크기에 상관없이 항상 동일한 시간이 걸립니다.
def get_first(arr):
return arr[0] # 인덱스 직접 접근
def is_even(n):
return n % 2 == 0 # 단순 연산
# 해시 테이블 접근
d = {"name": "Alice"}
name = d["name"] # O(1) - 해시 계산 후 직접 접근
O(log n) - 로그 시간
매 단계마다 탐색 범위가 절반씩 줄어듭니다.
def binary_search(arr, target):
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
# n=1,000,000 → 최대 약 20번 비교 (log₂(1,000,000) ≈ 20)
n=8: [1, 2, 3, 4, 5, 6, 7, 8] → 최대 3번 (log₂8 = 3)
n=16: 16개 항목 → 최대 4번 (log₂16 = 4)
n=1000000: 백만 개 → 최대 20번
O(n) - 선형 시간
입력 크기에 비례하여 실행 시간이 늘어납니다.
def linear_search(arr, target):
for item in arr: # 최악: 전체 순회
if item == target:
return True
return False
def find_max(arr):
max_val = arr[0]
for item in arr: # n번 순회
if item > max_val:
max_val = item
return max_val
O(n log n) - 선형 로그 시간
효율적인 정렬 알고리즘의 시간 복잡도입니다.
# 병합 정렬 (Merge Sort) - O(n log n)
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # log n 단계 분할
right = merge_sort(arr[mid:])
return merge(left, right) # 각 단계에서 O(n) 병합
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
O(n²) - 이차 시간
중첩 반복문에서 흔히 나타납니다.
# 버블 정렬 - O(n²)
def bubble_sort(arr):
n = len(arr)
for i in range(n): # 외부 루프: n번
for j in range(n-i-1): # 내부 루프: n-i-1번
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
# 모든 쌍 찾기
def find_pairs(arr, target_sum):
pairs = []
for i in range(len(arr)): # O(n)
for j in range(i+1, len(arr)): # O(n)
if arr[i] + arr[j] == target_sum:
pairs.append((arr[i], arr[j]))
return pairs # 전체 O(n²)
O(2ⁿ) - 지수 시간
피보나치를 순수 재귀로 구현할 때처럼 각 단계에서 호출이 2배씩 늘어납니다.
# 비효율적인 피보나치 - O(2ⁿ)
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2) # 각 호출이 두 개 생성
# 호출 트리:
# fib(5) → fib(4) + fib(3)
# fib(3) + fib(2) + fib(2) + fib(1)
# ... (지수적 증가)
O(n!) - 팩토리얼 시간
순열을 완전 탐색할 때 발생합니다.
def permutations(arr):
if len(arr) <= 1:
return [arr]
result = []
for i, item in enumerate(arr):
rest = arr[:i] + arr[i+1:]
for perm in permutations(rest): # (n-1)! 개의 순열
result.append([item] + perm)
return result
# n=10 → 3,628,800번 연산
# n=20 → 2,432,902,008,176,640,000번 연산 (사실상 불가)
성장률 비교
import math
complexities = {
"O(1)": lambda n: 1,
"O(log n)": lambda n: math.log2(n),
"O(n)": lambda n: n,
"O(n log n)": lambda n: n * math.log2(n),
"O(n²)": lambda n: n ** 2,
"O(2ⁿ)": lambda n: 2 ** n,
}
print(f"{'복잡도':<15} {'n=10':>15} {'n=100':>15} {'n=1000':>15}")
print("-" * 60)
for name, f in complexities.items():
try:
print(f"{name:<15} {f(10):>15,.0f} {f(100):>15,.0f} {f(1000):>15,.0f}")
except OverflowError:
print(f"{name:<15} {'너무 큰 값':>15}")
| 복잡도 | n=10 | n=100 | n=1,000 | n=1,000,000 |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 1 |
| O(log n) | 3 | 7 | 10 | 20 |
| O(n) | 10 | 100 | 1,000 | 1,000,000 |
| O(n log n) | 33 | 664 | 9,966 | 19,931,568 |
| O(n²) | 100 | 10,000 | 1,000,000 | 10¹² |
| O(2ⁿ) | 1,024 | 1.27×10³⁰ | 실질 불가 | 실질 불가 |
빅오 분석 실전 예제
복잡도 계산 규칙
# 규칙 1: 순차 실행 → 최대 복잡도
def example1(n):
for i in range(n): # O(n)
print(i)
for i in range(n * n): # O(n²)
print(i)
# 합산: O(n) + O(n²) = O(n²)
# 규칙 2: 중첩 → 곱셈
def example2(n):
for i in range(n): # O(n)
for j in range(n): # O(n)
print(i, j)
# 결과: O(n × n) = O(n²)
# 규칙 3: 독립적인 변수는 각각 표기
def example3(m, n):
for i in range(m): # O(m)
print(i)
for j in range(n): # O(n)
print(j)
# 결과: O(m + n)
공간 복잡도
# O(1) 공간: 변수 몇 개만 사용
def sum_array(arr):
total = 0 # 상수 개의 변수
for x in arr:
total += x
return total
# O(n) 공간: 입력 크기에 비례하는 추가 메모리
def copy_array(arr):
return arr[:] # n 크기의 새 배열 생성
# O(log n) 공간: 재귀 호출 스택 (이진 탐색)
def binary_search_recursive(arr, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid+1, right)
else:
return binary_search_recursive(arr, target, left, mid-1)
# 재귀 깊이: log n → 공간 복잡도 O(log n)
빅오 표기법이 중요한 이유
1. 대규모 데이터에서의 성능 예측
1초에 10억(10⁹) 연산 가능한 컴퓨터 기준:
n = 1,000,000 (백만) 데이터 처리 시:
O(log n): 약 0.00000002초 ← 즉각적
O(n): 약 0.001초 ← 빠름
O(n log n): 약 0.02초 ← 빠름
O(n²): 약 1,000초 ← 너무 느림!
O(2ⁿ): 우주 나이보다 오래 걸림
2. 알고리즘 선택의 기준
# 정렬 예: 같은 결과, 다른 성능
import time
import random
data = random.sample(range(1000000), 10000)
# O(n²) - 버블 정렬
start = time.time()
bubble_sort(data.copy())
print(f"버블 정렬: {time.time() - start:.3f}초")
# O(n log n) - Python 내장 정렬 (Tim Sort)
start = time.time()
sorted(data.copy())
print(f"Tim Sort: {time.time() - start:.3f}초")
주요 알고리즘 복잡도 요약
| 알고리즘/자료구조 | 평균 시간 복잡도 | 최악 시간 복잡도 | 공간 복잡도 |
|---|---|---|---|
| 배열 접근 | O(1) | O(1) | O(n) |
| 이진 탐색 | O(log n) | O(log n) | O(1) |
| 선형 탐색 | O(n) | O(n) | O(1) |
| 버블/삽입/선택 정렬 | O(n²) | O(n²) | O(1) |
| 병합/힙 정렬 | O(n log n) | O(n log n) | O(n)/O(1) |
| 퀵 정렬 | O(n log n) | O(n²) | O(log n) |
| 해시 테이블 조회 | O(1) | O(n) | O(n) |
| BST 탐색 | O(log n) | O(n) | O(n) |
| DFS/BFS | O(V+E) | O(V+E) | O(V) |
| 피보나치 (순수 재귀) | O(2ⁿ) | O(2ⁿ) | O(n) |
| 피보나치 (DP) | O(n) | O(n) | O(n) |