2025년 3월 16일
시간 복잡도, 공간 복잡도 (Time Complexity, Space Complexity)
1. 시간 복잡도와 공간 복잡도의 개요
(1) 시간 복잡도와 공간 복잡도의 개념
| 시간 복잡도 (Time Complexity) | 알고리즘의 효율성 측정을 위해 필요한 입력 데이터 대비 연산 시 수행 시간을 나타내는 척도 |
|---|---|
| 공간 복잡도 (Space Complexity) | 알고리즘의 효율성 측정 위해 프로그램 수행 시 사용되는 메모리 공간의 크기를 나타내는 척도 |
(2) 효율적 알고리즘을 위한 요소
| 시간 효율성 | 주어진 조건에서 문제 해결 위해 가능한 최소 시간 내 해결책을 찾는 요소 |
|---|---|
| 공간 효율성 | 프로그램 수행을 위해 가능한 최소 메모리를 관리하고 사용하는 요소 |
| 코드 효율성 | 사람이 빠르게 이해 및 수정하거나 컴파일러 및 하드웨어 최적화 요소 |
- 알고리즘 효율성을 판단하기 위해 시간 복잡도 및 공간 복잡도를 수치화하여 정량적으로 평가 가능
2. 시간 복잡도와 공간 복잡도의 측정 대상 및 방법
(1) 시간 복잡도의 측정 대상 및 방법
| 측정 대상 |  | |
|---|---|---|
| 측정 방법 | 빅오(O) 표기법 | 입력데이터의 최악을 기준으로 시간 복잡도를 측정 |
| 빅오메가(Ω) 표기법 | 입력데이터의 최선을 기준으로 시간 복잡도를 측정 | |
| 세타(Θ) 표기법 | O-표기와 Ω-표기가 같은 경우 시간 복잡도를 측정 | |
(2) 공간 복잡도의 측정 대상 및 방법
| 측정 대상 | 고정 공간 | 알고리즘과 무관한 공간. 코드 저장공간, 단순변수 및 상수 |
|---|---|---|
| 가변 공간 | 알고리즘 실행 관련 공간. 실행 중 동적으로 필요한 공간 | |
| 측정 방법 | Memory Layout 고려 | 데이터 구조 크기와 변수의 크기 등을 고려하여 측정 |
| 디버깅 도구 사용 | Xcode와 같은 디버깅 도구 사용하여 메모리 사용을 측정 |
- 일반적으로 복잡도가 낮으면 알고리즘 효율성(성능)이 우수하다고 판단 가능
3. 시간 복잡도와 공간 복잡도 비교
| 비교 항목 | 시간 복잡도 | 공간 복잡도 |
|---|---|---|
| 측정 대상 | 입력값에 따른 연산 시간을 측정 | 사용된 메모리 공간 크기를 측정 |
| 복잡도 계산 | Big-O/Ω 수식에 따라 계산 | 고정 공간 + 가변 공간 |
| 판단 기준 | 결과 수치가 작을 수록 효율적 | 메모리 공간 크기가 작을 수록 효율적 |
- 공간 복잡도는 실행되는 H/W, S/W 환경의 영향으로 달라질 수 있으며, 일반적으로 시간 복잡도(특히 빅오 표기법)를 사용하여 알고리즘 효율성을 판단
[참고]
- 이충기, KOCW, 알고리즘의 효율성 분석
- 양성봉, 생능출판사, 알기 쉬운 알고리즘, 2021
About The Author
