복잡도

1. 복잡도

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

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

• 시간 복잡도 : 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는가 (알고리즘을 위해 필요한 연산의 횟수)
• 공간 복잡도 : 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는가 (알고리즘을 위해 필요한 메모리의 양)

당연히 동일한 기능을 수행하는 알고리즘에서 복잡도가 낮을수록 좋은 알고리즘이다.

코테 알고리즘에서의 복잡도는 대부분 시간 복잡도를 의미한다.

 

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

빅오 표기법은 간단히 말해 가장 빠르게 증가하는 항만을 고려하는 표기법이다. (함수의 상한 값만 나타냄)

 

아래 소스코드의 시간복잡도는?

array = [3,5,1,2,4]

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

위 코드의 시간복잡도는 (데이터의 갯수가 N개라고 할 때) O(N^2) 이다. array 배열의 원소 수가 5개이므로, N = 5

2중 반복문을 이용하여 각 원소에 대해 다른 모든 원소에 대한 곱셈 결과를 매번 출력하고 있다. 사실 2중 반복문이기 때문에 N X N 만큼의 연산이 필요하다는 것을 유추할 수 있다.

 

시간 복잡도 표

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

위쪽에 있을 수록 더 빠르다. 

 

 2. 시간과 메모리 측정

파이썬에서는 프로그램 수행 시간과 메모리 사용량을 측정할 수 있다. 알고리즘의 소요시간을 확인해야 자신이 제대로 알고리즘을 작성하고 있는지 체크할 수 있다. 즉, 실제 프로그램의 수행 시간을 측정하는 것은 알고리즘의 효율성을 측정하는 가장 기본적인 방법이다.

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

# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time : ", end_time - start_time) # 수행 시간 출력

위와 같이 어떤 알고리즘을 설계한 뒤 시간 복잡도를 경험적으로 증명하고 싶을 때 위와 같은 형태의 코드를 자주 이용한다.