복잡도

복잡도, Complexity

복잡도는 알고리즘의 성능을 나타내는 척도이다.

복잡도는 크게 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눌 수 있다.

알고리즘 문제를 풀때, 단순히 '복잡도'라고 하면 보통은 시간 복잡도를 의미한다.

 

• 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다. 이를 측정함으로써 알고리즘을 위해 필요한 연산의 횟수를 계산할 수 있다.
• 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의마한다. 이를 측정함으로써 알고리즘을 위해 필요한 메모리의 양을 계산할 수 있다.

효율적인 알고리즘을 사용한다고 했을 때 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계(Trade-off)가 성립한다.

 

이때, 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 종종 있다. 실제로 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법으로 메모이제이션(Memoization) 기법이 있는데, 이 방법은 8장에서 다룰 예정이다.

 

 

빅오 표기법, Big-O

 

시간 복잡도와 공간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다.

 

시간 복잡도

다음과 같은 예제에서는 5개의 데이터에 비례하여 연산을 수행하기에 시간 복잡도가 O(N)이라고 표기한다.

array = [3, 5, 1, 2, 4] # 5개의 데이터(N = 5)
summary = 0 # 합계를 저장할 변수

# 모든 데이터를 하나씩 확인하며 합계를 계산
for x in array:
	summary += x
    
# 결과를 출력
print(summary)

 

다음과 같은 예제에서는 단순히 더하기 연산 한번 수행되기 때문에, 이는 상수 연산이므로 시간 복잡도는 O(1)로 표기한다.

a = 5
b = 7
print(a + b)

 

다음과 같은 예제에서는 2중 반복문으로 N x N 연산이 필요하여 시간복잡도는 O(N^2)으로 표기한다.

array = [3, 5, 1, 2, 4] # 5개의 데이터(N = 5)

for i in array:
	for j in array:
    	temp = i * j
        print(temp)

 

하지만 모든 2중 반복문의 시간 복잡도가 O(N^2)가 되는 것은 아니다.

만약 소스코드가 내부적으로 다른 함수를 호출한다면 내부 함수의 시간 복잡도까지 고려해야 한다.

 

6장에서 배우게 될 내용 중 하나인 퀵 정렬의 평균 시간 복잡도는 O(NlogN)이지만, 최악의 경우 시간 복잡도는 O(N^2)이다.

 

아래는 시간복잡도 표인데, 위쪽에 있을수록 빠르다.

빅오 표기법	명칭
O(1)	상수 시간(Constant time)
O(log N)	로그 시간(Log time)
O(N)	선형 시간
O(N log N)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^n)	지수 시간

 

더불어 컴퓨터 과학에서는 특정한 알고리즘의 시간 복잡도가 O(N^K)일 때(이때 K는 상수 값을 가진다). 이를 '다항 시간에 동작하는 알고리즘'이라고 말한다. 이차 시간, 삼차 시간 등이 모두 다항 시간에 해당한다.

 

일반적으로 코딩 테스트 환경에서는 O(N^3)을 넘어가면 문제 풀이에서 사용하기 어렵다.

	N이 1,000일 때의 연산 횟수
O(N)	1,000
O(N log N)	10,000
O(N^2)	1,000,000
O(N^3)	1,000,000,000

 

다음은 모두 시간 제한이 1초인 문제에 대한 예시이다.

• N의 범위가 500인 경우: 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 2,000인 경우: 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 100,000인 경우: 시간 복잡도가 O(N log N)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.

 

공간 복잡도

일반적으로 메모리 사용량 기준은 MB단위로 제시된다. 코딩 테스트에서는 보통 메모리 사용량을 128~512MB 정도로 제한한다.

 

 

시간과 메모리 측정

실제 프로그램의 수행 시간을 측정하는 것은 알고리즘의 효율성을 측정하는 가장 기본적인 방법이다.

 

특정한 프로그램의 수행 시간을 측정하는 소스코드 예시는 다음과 같다.

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

# 프로그램 소스코드...

end_time = time.time() # 측정 종료
print("time :", end_time - start_time) # 수행 시간 출력