알고리즘의 성능을 어떻게 판단할 수 있을까?
주로 복잡도(complextiy)의 개념으로 성능을 풀어낸다.
복잡도는 시간 복잡도(Time complexity)와 공간 복잡도(Space complexity)로 나눌 수 있다.
시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래걸리는 지를 의미하고
공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는 지를 의미한다.
좀 더 간단히 들여다보면
- 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수
- 공간 복잡도: 알고리즘을 위해 필요한 메모리의 양
으로 나타낼 수 있다. 보통은 두 복잡도는 서로 Trade off 관계가 성립한다.\
1. 시간 복잡도
시간복잡도를 설명할때는 빅오 표기법을 사용한다.
프로그램 내에서 연산되는 횟수를 괄호안에 표기함으로써 그 복잡도를 나타낸다.
대표적인 표기들로는 아래의 표와 같다.
2. 공간 복잡도
공간복잡도 또한 빅오로 표기하는데 역시 시간 복잡도에서 사용한 빅오 표기법과 동일하게 사용된다.
보통 코딩테스트는 메모리 사용량을 128 ~ 512 MB로 제한한다.
즉, 데이터 개수가 1,000만 단위를 넘지 않도록 알고리즘을 설계해야된다.
하지만 그럴일이 잘 없음으로 만약 1,000만 단위를 넘어가도록 설계했다면 본인이 틀렸는 지 의심해봐야한다.
3. 시간 복잡도 측정
특정 프로그램의 수행 시간을 측정하는 소스코드는 다음과 같다.
예)
import time
start_time = time.time() # 측정 시작
# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time :", end_time - start_time) # 수행 시간 출력
Ref) 이것이 코딩테스트다 with 파이썬, 동빈나 저
댓글