시간 복잡도, 공간 복잡도 (Time Complexity, Space Complexity)

1. 시간 복잡도와 공간 복잡도의 개요

(1) 시간 복잡도와 공간 복잡도의 개념

시간 복잡도 (Time Complexity)	알고리즘의 효율성 측정을 위해 필요한 입력 데이터 대비 연산 시 수행 시간을 나타내는 척도
공간 복잡도 (Space Complexity)	알고리즘의 효율성 측정 위해 프로그램 수행 시 사용되는 메모리 공간의 크기를 나타내는 척도

(2) 효율적 알고리즘을 위한 요소

시간 효율성	주어진 조건에서 문제 해결 위해 가능한 최소 시간 내 해결책을 찾는 요소
공간 효율성	프로그램 수행을 위해 가능한 최소 메모리를 관리하고 사용하는 요소
코드 효율성	사람이 빠르게 이해 및 수정하거나 컴파일러 및 하드웨어 최적화 요소

• 알고리즘 효율성을 판단하기 위해 시간 복잡도 및 공간 복잡도를 수치화하여 정량적으로 평가 가능

 

2. 시간 복잡도와 공간 복잡도의 측정 대상 및 방법

(1) 시간 복잡도의 측정 대상 및 방법

측정 대상
측정 방법	빅오(O) 표기법	입력데이터의 최악을 기준으로 시간 복잡도를 측정
	빅오메가(Ω) 표기법	입력데이터의 최선을 기준으로 시간 복잡도를 측정
	세타(Θ) 표기법	O-표기와 Ω-표기가 같은 경우 시간 복잡도를 측정

• 사례) 𝑂(2^N ): 동적 프로그래밍, 𝑂(𝑁² ): 버블 정렬, 𝑂(𝑁 log⁡𝑁 ): 퀵 정렬, 𝑂(𝑁): for 문, 𝑂(log⁡𝑁 ): 이진 트리, 𝑂(1): Hash

(2) 공간 복잡도의 측정 대상 및 방법

측정 대상	고정 공간	알고리즘과 무관한 공간. 코드 저장공간, 단순변수 및 상수
	가변 공간	알고리즘 실행 관련 공간. 실행 중 동적으로 필요한 공간
측정 방법	Memory Layout 고려	데이터 구조 크기와 변수의 크기 등을 고려하여 측정
	디버깅 도구 사용	Xcode와 같은 디버깅 도구 사용하여 메모리 사용을 측정

• 일반적으로 복잡도가 낮으면 알고리즘 효율성(성능)이 우수하다고 판단 가능

 

3. 시간 복잡도와 공간 복잡도 비교

비교 항목	시간 복잡도	공간 복잡도
측정 대상	입력값에 따른 연산 시간을 측정	사용된 메모리 공간 크기를 측정
복잡도 계산	Big-O/Ω 수식에 따라 계산	고정 공간 + 가변 공간
판단 기준	결과 수치가 작을 수록 효율적	메모리 공간 크기가 작을 수록 효율적

• 공간 복잡도는 실행되는 H/W, S/W 환경의 영향으로 달라질 수 있으며, 일반적으로 시간 복잡도(특히 빅오 표기법)를 사용하여 알고리즘 효율성을 판단

 
[참고]

• 이충기, KOCW, 알고리즘의 효율성 분석
• 양성봉, 생능출판사, 알기 쉬운 알고리즘, 2021