시간/공간 복잡도와 Big-O 표기법

시간 복잡도는 현재 입력된 크기 n에 대한 알고리즘의 실행 시간이다. 이를테면 길 찾기 알고리즘을 실행한다고 할 때, 가장 빠른 길은 최선 케이스가 될 것이다. 적당히 돌아간다면 평균 케이스, 그리고 정말 최악의 케이스 역시 존재할 것이다. 일반적으로 Big-O는 최악의 케이스를 분석한다. 해당 최악의 케이스는 알고리즘의 성능으로 들어갈 것이다.

 

 

공간 복잡도는 현재 입력된 크기 n에 대한 알고리즘의 메모리 사용량이다. 공간 복잡도는 입력 공간, 보조 공간, 출력 공간으로 구분할 수 있다. 이 중 우리는 주로 보조 공간을 분석하게 될 것이다. 보조 공간은 알고리즘이 실행되는 동안 임시로 사용되는 공간이라 이해하면 된다. 이 공간은 입력 공간을 포함하지 않기에, 순수하게 현재 메모리가 얼마나 사용되고 있는지를 파악하기에 유용해 이걸로 알고리즘 성능을 판단할 수 있다. 공간 복잡도 역시 Big-O 표기법을 이용해 복잡도를 표기할 수 있다. 

 

백준 문제들을 보다보면 시간 제한과 메모리 제한이 나오는데, 이게 각각 시간 복잡도와 공간 복잡도에 관련된 것이라 생각하면 된다.

 

 

 

아래 표는 Big-O 표기법을 정리한 것이다

 

예시를 통해 표기법을 확인해보자. 파이썬 코드이다

def func(arr, target):
 	for i in range(len(arr)):
 		if arr[i] == target:
 			return i
 return -1

우선 무엇이 n인가? 여기에서는 len(arr)이 n이 될 것이다. 그리고 최악의 경우 target을 찾기 위해 최대 n번의 반복문이 필요할 것이다. 그렇기에 시간 복잡도는 O(n)이다. 그리고 딱히 추가적인 메모리를 잡아먹지 않고 있는 정보만 사용해서 탐색하기에 공간 복잡도는 O(1)이다. 

 

def func(arr, target, left, right):
 	if left > right:
 		return -1
 mid = (left + right) // 2
	 if arr[mid] == target:
 		return mid
 elif arr[mid] < target:
 	return func(arr, target, mid + 1, right)
 else:
	 return func(arr, target, left, mid - 1)

이번에는 재귀를 포함한 이진 탐색 함수이다. 매번 재귀를 반복할 때마다 탐색 범위가 절반으로 줄어들고 있다. 그렇기에 시간 복잡도는 O(log n)이다. 공간 복잡도는 어떨까? 사용하고 있는 변수는 계속 동일하지만, 재귀로 함수를 다시 호출할 때마다 재귀 호출 스택에 log n개의 함수 프레임이 저장되고 있다. 그렇기에 공간 복잡도 역시 O(log n)이다.