코딩테스트를 준비하거나 문제를 풀 때, 알고리즘의 시간 복잡도를 이해하고 계산하는 건 정말 중요합니다. 오늘은 시간 복잡도가 뭔지, 어떻게 계산하는지, 실제 예제 문제와 계산 팁까지 모두 정리해보겠습니다. 이걸 잘 익히면 문제를 푸는 데 훨씬 큰 도움이 될 것입니다.
1. 시간 복잡도란?
시간 복잡도(Time Complexity)는 알고리즘이 실행되는 데 필요한 시간의 증가율을 나타내는 지표입니다. 입력 크기(n)가 커질수록 알고리즘이 얼마나 효율적으로 동작하는지를 보여줍니다. 쉽게 말해, 입력 크기가 커질 때 실행 시간이 얼마나 늘어나는지를 파악하는 겁니다.
2. 대표적인 시간 복잡도 표기법
시간 복잡도는 보통 빅오 표기법(Big-O Notation)으로 표현합니다. 아래 표에 주요 시간 복잡도와 그 특징들을 정리했습니다:
| 표기법 | 설명 | 예시 |
| O(1) | 상수 시간 (입력 크기에 무관) | 배열의 특정 인덱스 접근 |
| O(log n) | 로그 시간 (반씩 줄어듦) | 이진 탐색 |
| O(n) | 선형 시간 | 단일 for문 |
| O(n log n) | 선형 로그 시간 | 합병 정렬, 퀵 정렬 (평균) |
| O(n^2) | 이차 시간 | 중첩된 이중 for문 |
| O(2^n) | 지수 시간 | 피보나치 수 재귀 풀이 |
| O(n!) | 팩토리얼 시간 | 순열 생성 |
3. 시간 복잡도 계산법
시간 복잡도를 계산은 아래 순서로 진행하면 좋습니다:
- 가장 중첩된 루프부터 분석:
- 예를 들어, 이중 for문은 O(n^2)가 됩니다.
- 주요 연산 확인:
- 조건문, 배열 접근, 함수 호출 등 실행에 걸리는 시간을 체크하세요.
- 상수 항 제거:
- O(2n + 3)은 O(n)으로 단순화합니다. 중요한 건 증가율이니까요.
- 가장 높은 차수만 남김:
- O(n^2 + n)은 O(n^2)로 표기합니다.
4. 시간 복잡도 계산 문제
아래 문제들을 통해 직접 시간 복잡도를 계산해보며 개념을 익히겠습니다.
문제 1: 단일 for문
def single_loop(n):
for i in range(n):
print(i)- 해설: for문이 n번 반복되므로 O(n)
문제 2: 중첩 루프
def nested_loops(n):
for i in range(n):
for j in range(n):
print(i, j)- 해설: 이중 for문이므로 O(n^2)
문제 3: 이진 탐색
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right)<em> // 2</em>
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1- 해설: 탐색 범위가 반씩 줄어드므로 O(log n)
문제 4: 병합 정렬
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr)<em> // 2</em>
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)- 해설: 각 단계에서 merge시 O(n), 재귀 함수를 통해 merge_sort가 호출되는 횟수가 O(log n) -> O(n log n)
문제 5: 순열 생성
def permutations(arr):
if len(arr) == 0:
return [[]]
result = []
for i in range(len(arr)):
for p in permutations(arr[:i] + arr[i+1:]):
result.append([arr[i]] + p)
return result- 해설: 순열의 수는 n!이므로 O(n!)
5. 시간 복잡도 계산 팁
- 루프를 먼저 분석하자:
- 모든 for문과 while문이 몇 번 반복되는지 따져보세요.
- 재귀 호출 단계 확인:
- 재귀 함수는 호출 횟수와 각 호출에서의 작업을 계산해야 합니다.
- 조건문도 신경 쓰자:
- 특정 조건에서만 실행되는 코드라도 최악의 경우를 고려하세요.
- 정렬 알고리즘 기본은 O(n log n):
- 대부분의 정렬 문제는 이 복잡도를 가집니다.
- 문제 유형별 암기:
- 이진 탐색: O(log n)
- 순열 생성: O(n!)
- 단일 for문: O(n)
