시작하며,
이실직고를 하자면, 지금까지 알고리즘 공부를 소홀히 하기도 했고,,,
이론 공부보다는 일단 냅다 개발해보는 성격이라 슬슬 공부의 필요성을 느끼기 시작하긴 했다
이런저런 일들이 많이 있었는데 아무튼 이제는 진짜 해야겠다 싶어서 차근차근 이론 공부를 시작해볼까 한다
개요
알고리즘의 효율성을 평가하는 핵심 지표인 시간복잡도와 공간복잡도에 대해 알아보자
두 개념은 프로그램이 실행될 때 입력 크기(n)가 커짐에 따라 연산 횟수와 메모리 사용량이 어떻게 변하는지를 수학적으로 표현하는 도구이다
입력의 크기가 작을 땐 알고리즘 간의 차이가 미미해보일 수 있지만,
입력의 크기가 1만, 10만, 100만으로 커질수록 시간복잡도와 공간복잡도의 차이는 기하급수적으로 커지며, 결과적으로 실행 속도와 자원 사용 효율에 큰 영향을 미치게 된다
Big-O 표기법
Big-O 표기법은 시간복잡도와 공간복잡도를 같은 언어로 표현하기 위한 공통 지표이다
즉, 어떤 알고리즘이 입력 크기(n)에 따라 얼마나 많은 연산을 수행하고, 얼마나 많은 메모리를 사용하는지를 Big-O 표기법으로 간결하게 나타낼 수 있다
| 표기 | 명칭 | 예시 | 설명 |
|---|---|---|---|
| O(1) | 상수 시간 | Hash Table Lookup | 입력 크기와 무관 |
| O(log n) | 로그 시간 | Binary Search | 입력이 커져도 완만한 증가 |
| O(n) | 선형 시간 | 단일 반복문 | 입력 크기에 비례 |
| O(n log n) | 로그선형 | Merge Sort, Quick Sort | 효율적인 정렬 |
| O(n²) | 이차 시간 | 중첩 반복문 | 입력 2배 → 연산 4배 |
| O(2ⁿ), O(n!) | 지수/팩토리얼 | 재귀 탐색, 순열 생성 | 급격히 증가 |
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
시간복잡도와 공간복잡도 모두 "입력 크기가 커질 때 성능이 얼마나 빠르게 악화되는가" 를 나타내며, 알고리즘의 효율성을 정량적으로 비교할 수 있게 만들어준다
Big-O 표기법의 특징
상수와 작은 항 무시
Big-O 표기법은 입력 크기(n)가 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 입력 크기(n)에 따라 영향을 받기 때문에 상수항 같은 사소한 부분은 무시한다
예시
O(2n) -> O(n)
O(3n + 2) -> O(n)
최악의 경우를 기준으로 표기
Big-O 표기법은 보통 알고리즘이 가장 오래 걸리는 최악의 상황을 기준으로 표현한다
공간복잡도를 계산할 때도 마찬가지로, 가장 많은 메모리를 사용하는 최악의 상황을 기준으로 표현한다
이렇게 하면 어떤 입력이 주어지더라도 수행 시간과 메모리 사용량이 절대 그보다 더 나빠지지 않는다는 보장을 줄 수 있다
예시
정렬 알고리즘 중 퀵정렬은 평균적으로 O(n log n)이지만, 최악의 경우 O(n²)으로 표기된다
가장 큰 항으로 표현
입력 크기가 커질수록 연산량에 가장 큰 영향을 주는 항만 남기고, 나머지 작은 항들은 무시한다
전체 연산량의 증가 속도를 결정하는 핵심 요소가 가장 큰 항이기 때문이다
예시
O(n² + n) -> O(n²)
중첩 구조 고려
시간복잡도의 경우, 반복문이 중첩되면 각 반복문의 수행 횟수를 곱하고, 순차로 실행되면 수행 횟수를 더한다
예시
중첩 for문 -> n * n = O(n²)
순차 for문 2개 -> n + n = O(n)
참고 (공간복잡도)
- 재귀 호출의 경우 스택의 깊이도 공간복잡도에 포함된다
- “입력 데이터 자체 크기”는 보통 제외하고, 추가로 필요한 메모리만 측정한다
시간복잡도와 공간복잡도 구하는 법
예시 1: 단일 반복문
def example(n):
for i in range(n):
print(i)시간복잡도: O(n)
공간복잡도: O(n)
예시 2: 중첩 반복문
def example(n):
for i in range(n):
for j in range(n):
print(i, j)시간복잡도: O(n²)
공간복잡도: O(n)
예시 3: 로그 반복문
def example(n):
i = 1
while i < n:
print(i)
i *= 2시간복잡도: O(log n)
공간복잡도: O(n)
예시 4: 재귀 기반 이진탐색
def binary_search(arr, target, low, high):
if low > high:
return -1 # 찾지 못함
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr, target, low, mid - 1)
else:
return binary_search(arr, target, mid + 1, high)시간복잡도: O(log n)
공간복잡도: O(log n)
예시 5: 공간복잡도 추가 예시
# O(1) - 변수 하나만 사용
sum = 0
# O(n) - 입력 크기만큼 배열 사용
arr = [n for i in n]
# O(n²) - n*n 만큼의 이차원 배열
arr2 = [[0 for _ in range(n)] for _ in range(n)]알고리즘 효율 비교 방법
| 비교 항목 | 설명 |
|---|---|
| 시간복잡도 | 입력 증가에 따른 연산량 변화 |
| 공간복잡도 | 필요한 메모리 크기 |
| Trade-off | 더 빠른 속도를 위해 메모리를 더 쓰거나, 반대의 경우 발생 |
| 입력 크기(n) | 실제 데이터 규모에 따라 효율이 달라질 수 있음 |
알고리즘 효율이 데이터의 크기에 따라 달라지는 경우도 있다
정렬할 데이터가 작으면 O(n²) 정렬이 더 빠를수도 있고, 데이터가 클수록 O(n log n) 정렬이 유리하다
마치며,
빅데이터 환경에서는 시간복잡도, 공간복잡도보다 캐시, 병렬화 가능성, I/O 병목 등이 더 중요할 때도 있어서, 복잡도는 이론적인 기준선이지 절대적인 성능 기준은 아니라고 한다
다만 복잡도를 이해하면 코드의 개선 방향과 근거를 조금더 구체적으로 제시할 수 있을 것 같다
이번엔 여러 블로그글과 GPT의 힘을 좀 빌려서 공부를 해보았다
예시가 궁금할 때 GPT에게 물어보면 알려줘서 시간을 들여 찾을 필요는 없지만,
직접 이렇게 저렇게 계산해보는 시간이 비교적 적어지기는 해서
이론 공부할 때 GPT를 어느정도 활용할지 조금 고민해봐야겠다
이제 이론은 공부했으니,
알고리즘 문제 풀때마다 시간복잡도, 공간복잡도 구해보는 연습을 해봐야겠다
