알고리즘이 커진 입력 크기에 대해 얼마나 빠르게 실행되는지 분석하는 방법.
성능을 비교할 때 가장 중요한 지표로 사용된다.
시간복잡도를 이해하는 방법
📌 비유로 쉽게 이해하기
배달 음식 주문을 생각해 보자.
- A 음식점은 한 번에 하나씩 배달한다.
- B 음식점은 오토바이를 여러 대 써서 한 번에 여러 개 배달한다.
- C 음식점은 드론을 사용해서 순식간에 배달한다.
- ✔ A 음식점(비효율적인 알고리즘) → O(N²)
- ✔ B 음식점(보통의 알고리즘) → O(N log N)
- ✔ C 음식점(효율적인 알고리즘) → O(N) 또는 O(log N)
즉, 알고리즘마다 같은 문제를 해결해도 처리 속도가 다른걸 알 수 있다!
이를 수학적으로 표현한 것이 시간복잡도(Big-O 표기법)
시간복잡도 표기법 (Big-O 표기법)
빅오(Big-O) 표기법은 최악의 경우(가장 느린 경우)의 실행 시간을 표현합니다.
시간복잡도를 예제 코드로 이해하기
O(1) → 상수 시간 (입력 크기와 관계없이 일정한 시간)
def get_first_element(arr):
return arr[0] # 배열의 첫 번째 원소 접근 (항상 1번 실행)✔ 특징: 배열의 크기 N이 커져도 실행 시간은 변하지 않음.
O(N) → 선형 시간 (입력 크기에 비례)
def print_all_elements(arr):
for element in arr:
print(element) # 배열의 크기만큼 실행 (N번 반복)✔ 특징: 배열이 커질수록 실행 시간도 증가.
O(N²) → 이차 시간 (입력 크기만큼 반복 × 반복)
def print_pairs(arr):
for i in range(len(arr)):
for j in range(len(arr)): # 중첩 루프
print(arr[i], arr[j])✔ 특징: N = 1000이면 1000 × 1000 = 1,000,000번 실행됨.
✔ 문제: N이 커지면 너무 느려짐 → 최적화 필요.
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✔ 특징: 매번 탐색 범위가 절반으로 줄어들어 O(log N)의 성능.
✔ 예제: N = 1,000,000이면 log(1,000,000) ≈ 20번만에 찾음.
O(2^N) → 지수 시간 (매우 느림)
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2) # 2개의 재귀 호출 발생✔ 특징: N이 조금만 커져도 실행 시간이 엄청 증가.
✔ 예제: N = 50이면 거의 10^15번 연산 → 실제 실행 불가능!
각 시간복잡도의 실제 실행 속도 비교
🔹 결론
✔ O(N log N) 이하의 알고리즘을 사용하는 것이 가장 좋음
✔ O(N²) 이상이면 N이 커질수록 실행 시간이 급격히 증가 → 최적화 필수
✔ O(2^N), O(N!) 알고리즘은 현실적으로 사용 불가능
.
.
.
.
우리는 왜 시간복잡도를 고려해야할까?
- 알고리즘 문제 풀이: N ≤ 10^6일 경우 O(N log N) 이하면 통과 가능.
- 웹 개발: 데이터베이스 검색 시 O(N²)보다 O(log N)이 훨씬 빠름.
- AI & 머신러닝: 모델 훈련 시 O(N log N) 이하의 최적화 필수.
다음과 같이 대부분 모든 영역에서 시간복잡도를 활용한다. 시간복잡도를 잘 활용하면 더 성능 좋은 서비스를 개발할 수 있지 않을까?
.
.
.
.
결론
✔ 시간복잡도가 작은 알고리즘을 선택해야 실행 속도가 빠름!
✔ 입력 크기에 따라 알고리즘을 선택하는 것이 중요!
.
.
.
이 글을 읽고 시간복잡도에 대해 어느정도 감이 잡혔길 바란다 !
Before Sunrise