알고리즘 복잡도

알고리즘 복잡도(Algorithm Complexity)는 알고리즘이 수행하는 연산의 수와 사용되는 자원의 양을 분석하여 성능을 평가하는 개념이다. 복잡도는 일반적으로 실행 시간(Time Complexity)과 공간 사용량(Space Complexity)으로 나뉜다.

1 개요

알고리즘 복잡도는 입력 크기(n)에 따라 알고리즘이 얼마나 효율적으로 실행되는지를 평가하는 척도이다. 주요 분석 요소는 다음과 같다.

• 시간 복잡도(Time Complexity) - 입력 크기에 따른 연산 횟수를 측정.
• 공간 복잡도(Space Complexity) - 입력 크기에 따른 메모리 사용량을 측정.
• 최선/평균/최악의 경우 분석 - 특정 입력 조건에서의 성능을 평가.

2 시간 복잡도(Time Complexity)

시간 복잡도는 알고리즘이 실행되기까지 수행해야 하는 기본 연산의 횟수를 나타낸다. 일반적으로 빅-오 표기법(Big-O Notation)을 사용하여 표현한다.

2.1 시간 복잡도의 표기법

시간 복잡도는 입력 크기 n에 대한 함수로 표현되며, 가장 큰 차수의 항만 남겨서 분석한다.

• O(1) - 상수 시간(Constant Time)
  • 특정 입력 크기에 관계없이 일정한 시간이 걸림 (예: 배열의 첫 번째 원소 접근).
• O(log n) - 로그 시간(Logarithmic Time)
  • 입력 크기가 증가할수록 실행 시간이 느리게 증가 (예: 이진 탐색).
• O(n) - 선형 시간(Linear Time)
  • 입력 크기에 비례하여 실행 시간이 증가 (예: 배열 탐색).
• O(n log n) - 선형 로그 시간(Linearithmic Time)
  • 입력 크기에 log n을 곱한 시간 복잡도 (예: 병합 정렬, 퀵 정렬 평균 경우).
• O(n²) - 이차 시간(Quadratic Time)
  • 입력 크기의 제곱에 비례하여 실행 시간이 증가 (예: 버블 정렬, 삽입 정렬).
• O(2ⁿ) - 지수 시간(Exponential Time)
  • 입력 크기가 커질수록 실행 시간이 급격히 증가 (예: 피보나치 수열 재귀).
• O(n!) - 계승 시간(Factorial Time)
  • 입력 크기 n! 만큼 연산이 필요 (예: 브루트 포스 순열 생성).

2.2 알고리즘별 시간 복잡도 예시

• 탐색
  • 선형 탐색(Linear Search) - O(n)
  • 이진 탐색(Binary Search) - O(log n)
• 정렬
  • 버블 정렬(Bubble Sort) - O(n²)
  • 퀵 정렬(Quick Sort) - O(n log n) (평균)
  • 병합 정렬(Merge Sort) - O(n log n)
• 그래프 알고리즘
  • 다익스트라 알고리즘(Dijkstra's Algorithm) - O(V²) 또는 O((V+E) log V) (우선순위 큐 사용 시)
  • 플로이드-워셜 알고리즘(Floyd-Warshall) - O(V³)

3 공간 복잡도(Space Complexity)

공간 복잡도는 알고리즘이 실행될 때 사용하는 추가 메모리 공간을 측정하는 개념이다.

• O(1) - 추가 메모리 없이 실행 가능 (예: 변수 하나만 사용하는 알고리즘).
• O(n) - 입력 크기에 비례하여 메모리 사용 (예: 리스트 저장).
• O(n²) - 행렬을 저장하는 경우 발생 (예: 그래프의 인접 행렬).

3.1 재귀 호출의 공간 복잡도

재귀 알고리즘에서는 추가적으로 호출 스택(Stack Space)이 필요하다. 예를 들어, 피보나치 재귀 호출은 O(n) 만큼의 추가 메모리를 소비한다.

4 최선, 평균, 최악의 경우 분석

알고리즘의 성능을 평가할 때는 다양한 입력에 대해 다음과 같은 경우를 분석한다.

• 최선의 경우(Best Case) - 알고리즘이 가장 빠르게 수행되는 경우.
• 평균적인 경우(Average Case) - 일반적인 입력을 고려한 실행 시간.
• 최악의 경우(Worst Case) - 실행 시간이 가장 오래 걸리는 경우.

예를 들어, 퀵 정렬(Quick Sort)의 시간 복잡도는 다음과 같다.

• 최선: O(n log n) (균등한 피벗 분할)
• 평균: O(n log n)
• 최악: O(n²) (이미 정렬된 경우, 최악의 피벗 선택)

5 빅-오 표기법(Big-O Notation)의 특징

• 상수 계수 무시 - O(2n) → O(n), O(3n²) → O(n²)
• 낮은 차수 무시 - O(n² + n) → O(n²)
• 곱셈 연산 유지 - O(n log n) 유지

6 복잡도 비교

다음은 주요 시간 복잡도 비교표이다.

알고리즘 복잡도 비교

복잡도	입력 크기 10	입력 크기 100	입력 크기 1000
O(1)	1	1	1
O(log n)	3.3	6.6	10
O(n)	10	100	1000
O(n log n)	33	660	10000
O(n²)	100	10000	1000000
O(2ⁿ)	1024	1.26×10³⁰	1.07×10³⁰⁰

7 알고리즘 복잡도 최적화 방법

• 데이터 구조 최적화 - 배열 대신 해시 테이블 사용 등.
• 동적 프로그래밍 적용 - 중복 연산을 줄여서 시간 단축.
• 분할 정복 기법 활용 - 문제를 작은 부분으로 나누어 해결.

8 같이 보기

• 시간 복잡도
• 공간 복잡도
• 빅오 표기법
• 정렬 알고리즘
• 검색 알고리즘