Python x 알고리즘 : 복잡도

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

복잡도는 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나뉜다.

동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.

 

시간 복잡도

특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다.

- 알고리즘을 위해 필요한 연산의 횟수를 계산

• 코딩 테스트에서 단순히 "복잡도"라 하면 보통 시간 복잡도를 의미한다.
• 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미한다.
• 코딩테스트에서 프로그램을 비효율적으로 작성하여 시간 제한을 넘기면 "시간 초과"라는 메세지와 함께 오답으로 처리된다.
• 시간 복잡도를 표현할 때는 빅오(Big-O)표기법을 사용한다.

빅오(Big-O)표기법이란 차수가 가장 큰 항만 남기는 것

3N³ + 5N² + 1,000,000
시간복잡도 O(N³)

 

예시로 아래 코드를 보자

//이 소스코드의 연산 횟수는 1이다. 따라서 시간 복잡도는 O(1)로 표현할 수 있다.
a = 1
b = 9
print(a+b)


//소스코드의 데이터의 갯수가 N개일 때 시간 복잡도는 O(N^2)로 표현할 수 있다.
array = [1, 2, 3, 4, 5]

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

시간제한에 따른 알고리즘 설계

500	O(N³)
2,000	O(N²)
100,000	O(NlogN)
10,000,000	O(N)

• 문제를 해석하기 전에 조건을 먼저 보고, 사용할 알고리즘을 먼저 분석하는 경우도 있다.
•  

공간 복잡도

특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.

- 알고리즘을 위해 필요한 메모리의 양을 계산

• 공간 복잡도를 표기할 때도 시간 복잡도를 표기한 것 처럼 빅오 표기법을 사용한다.
• 시간 복잡도에서 시간에 대한 제한이 있던 것 처럼 메모리 사용량에 절대적인 제한이 있다.
• 일반적으로 메모리 사용량 기준은 MB단위로 제시된다.

int a[1000]	4KB
int a[1000000]	4MB
int a[2000][2000]	16MB

• 코딩 테스트에서는 보통 메모리 사용량을 128~512MB 정도로 제한한다. 이 말은 일반적인 경우 데이터의 개수가 1000만 단위가 넘어가지 않도록 설계해야 한다는 것이다.

수행 시간 측정 코드

• 프로그램 수행 시간과 메모리 사용량을 측정하는 방법이다.

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

# 프로그램 소스코드

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