복잡도(Complexity) 개념 총 정리

복잡도란?

알고리즘의 성능을 나타내는 척도이다. 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다. 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있다. 시간 복잡도는 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지를 의미하고, 공간 복잡도는 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.

복잡도의 측정은 다음 2가지를 통해 진행한다.

• 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수
• 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양

효율적인 알고리즘을 사용한다는 가정 하에, 시간 복잡도와 공간 복잡도는 Trade-off가 성립한다. 메모리를 조금 더 많이 사용하면 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다.

 

 

시간 복잡도

알고리즘 문제를 풀 때, 단순히 복잡도라고하면 보통은 시간 복잡도를 의미한다. 처음 코딩 테스트를 접하는 사람들이 가장 어렵게 느끼는 부분이 ‘시간 제한’이며, 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미한다. 해당 시간 안에 동작하는 프로그램을 작성해야 정답 판정을 받을 수 있으며, 프로그램을 비효율적으로 작성하여 시간 제한을 넘기면 ‘시간 초과Time Limit Exceedeed’라는 메시지와 함께 오답으로 처리된다.

시간 복잡도는 빅오(BIG-O) 표기법을 사용한다. 가장 빠르게 증가하는 항만을 고려하는 표기법으로, 함수의 상한만을 표시한다.

빅오 표기법은 다음과 같다.

• O(1) : 상수 시간(Constant time)
• O(logN) : 로그 시간(Log time)
• O(N) : 선형 시간
• O(NlogN) : 로그 선형 시간
• O(N^2) : 이차 시간 ..

다만, 빅오 표기법이 절대적인 것은 아니라는 것은 알아만 두자.

일반적으로 코딩테스트 환경에서는 O(N^3)을 넘어가면 문제 풀이에서 사용하기 어렵다. 코딩 테스트 문제에서 시간 제한은 보통 1~5초 가량이므로 연산 횟수가 10억을 넘어가면 오답 판정을 받을 수 있다. 만약 N이 1000이면, N^3은 10억이다.

보통 시간 복잡도에서 ‘연산’은 프로그래밍 언어에서 지원하는 사칙 연산, 비교 연산 등과 같은 기본 연산을 의미한다.

시간 복잡도 분석은 문제 풀이의 핵심이다. 문제를 해석하기 전에 조건을 먼저 보기도 한다. 예를 들어, 데이터의 개수 N이 1000만 개를 넘어가며 시간 제한이 1초라면, 최악의 경우 O(N)의 시간 복잡도로 동작하는 알고리즘을 작성해야 한다. 혹은 데이터의 크기나 탐색 범위가 100억이나 1000억을 넘어가는 경우 이진 탐색과 같이 O(logN)의 시간 복잡도를 갖는 알고리즘을 작성해야 할 것이다. 다음은 시간 제한이 1초인 문제에 대한 시간 복잡도 조건의 예시이다.

• N의 범위가 500인 경우 : O(N^3)인 알고리즘을 설계하면 풀 수 있다.
• N의 범위가 2000인 경우 : O(N^2)인 알고리즘을 설계하면 풀 수 있다.
• N의 범위가 100,000인 경우 : O(NlogN)알고리즘을 설계하면 풀 수 있다.
• N의 범위가 10,000,000인 경우 : O(N)알고리즘을 설계하면 풀 수 있다.

 

 

공간 복잡도

공간 복잡도를 표기할 때도 시간 복잡도를 표기했던 것처럼, 빅오 표기법을 사용한다. 시간 복잡도의 1초 제한처럼, 공간 복잡도에도 메모리 사용량 제한이 있다. 메모리 사용량 기준은 MB단위로 제시되며, 시간 복잡도와 함께 ‘시간 제한 1초, 메모리 제한 128MB’와 같이 조건이 제시된다. 코딩 테스트 문제는 대부분 리스트(배열)을 사용해서 풀어야 한다.

메모리 사용량은 보통 128MB~512MB 정도로 제한한다. 다시 말해, 일반적인 경우 데이터의 개수가 1000만 단위가 넘어가지 않도록 알고리즘을 설계해야 한다.

 

 

시간 및 메모리 측정 방식

파이썬에서는 프로그램의 수행 시간과 메모리 사용량을 측정할 수 있다. 알고리즘을 공부하는 과정에서 시간을 측정하는 작업을 굉장히 많이 사용해야 한다.

import time
start_time = time.time() #측정 시작

######################################

#소스 코드

####################################

end_time = time.time() #측정 종료
print("time :", end_time - start_time)

수행 시간 측정 소스코드의 형태는 일반적으로 위와 같으며, 시간 복잡도를 경험적으로 증명하고 싶을 때 위와 같은 형태로 이용하자.

예를 들어, 선택 정렬과 파이썬의 기본 정렬 라이브러리의 속도를 비교할 때 다음과 같이 소스코드를 작성해보자. 선택정렬은 최악의 경우 시간 복잡도가 O(N^2)이며, 파이썬 기본 정렬 라이브러리는 최악의 경우 시간 복잡도 O(NlogN)이다.

from random import randint
import time

#배열에 정수 10,000개의 정수를 삽입
array = []
for _ in range(10000):
	array.append(randint(1,100))

start_time = time.time()

#선택정렬
for i in range(len(array)):
	min_index = i
	for j in range(i+1, len(array)):
		if array[min_index] > array[j]:
			min_index = j
	array[i],array[min_index] = array[min_index], array[i] 

end_time = time.time()
print(end_time - start_time)

start_time2 = time.time()

#기본 정렬
array.sort()

end_time2 = time.time()
print(end_time2 - start_time2)