시간 복잡도와 Big-O

Big-O가 뭔가요?

시간 복잡도$Time Complexity$는 입력 크기$n$에 따라 알고리즘의 실행 시간이 어떻게 증가하는지를 수학적으로 표현한 것이고, 그걸 나타내는 게 Big-O 표기법입니다.

 

예를 들어, 리스트에서 값을 찾는 코드를 보겠습니다.

def find_value(arr, target):
	for i in arr:
    	if i == target:
        	return True
    return False

 

 

 

이 함수는 arr에 값이 있을 때까지 앞에서부터 하나씩 검사하죠.
입력 길이 n이 길어질수록 비교 횟수도 많아져요.
=> O$n$, 즉 선형 시간 복잡도.

---

자주 쓰이는 시간 복잡도 예시

Big-O	설명	예시
O$1$	입력 크기에 상관없이 실행 시간 일정	딕셔너리 key조회
O$log n$	절반씩 줄이면서 탐색	이진 탐색
O$n$	모든 요소를 한 번씩	선형 탐색
O$n log n$	정렬 알고리즘의 평균	병합 정렬, 퀵 정렬
O$n²$	이중 반복문	버블 정렬
O$2ⁿ$, O$n!$	매우 비효율적	피보나치$재귀$, 순열 생

---

실행 시간 비교

import time

def constant_time():
    return 42

def linear_time(n):
    for _ in range(n):
        pass

def quadratic_time(n):
    for _ in range(n):
        for _ in range(n):
            pass

for n in [1000, 10000, 20000]:
    start = time.time()
    linear_time(n)
    end = time.time()
    print(f"O(n) with n={n}: {end - start:.6f} sec")

    start = time.time()
    quadratic_time(n)
    end = time.time()
    print(f"O(n^2) with n={n}: {end - start:.6f} sec")
    
    
    
# O(n) with n=1000: 0.000035 sec
# O(n^2) with n=1000: 0.087654 sec

 

작은 입력에서는 큰 차이가 없지만, n이 커질수록 O$n²$은 엄청 느려집니다.

---

실무에서 왜 중요할까?

• 검색 속도: 사용자 100만 명 중 특정 ID 찾을 때, O$n$ vs O$1$의 차이
• 정렬/필터링: API 서버에서 정렬을 맡길지, DB에서 처리할지 판단 기준
• 메모리 효율까지 고려: 시간 복잡도뿐 아니라 공간 복잡도도 함께 고려
•  

---

정리

기억할 것	설명
시간 복잡도는 "성능의 나침반"	알고리즘 효율을 비교하는 기준
Big-O는 최악의 경우를 표현	평균이나 최선은 따로 분석할 수도
Python은 느릴 수 있다	시간복잡도는 동일해도 언어 차이로 느릴 수 있