Python 알고리즘의 성능 평가

복잡도(Complexity)

---

• 시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
• 공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

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

 

 

빅오 표기법(Big-O Notation)

---

가장 빠르게 증가하는 항만을 고려하는 표기법  (함수의 상한만을 나타냄)

 

▶ 표현 방법

• n이 증가할 때 가장 빨리 증가하는 항(최고차 항)만 남기고 다른 항은 모두 생략
• 가장 빨리 증가하는 항에 곱해진 상수 역시 생략
• 남은 항을 O() 안에 넣어 표기

알고리즘 설계 Tip

---

▶ 일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우

•  C언어를 기준으로 통상 1~3초 가량 시간 소요
•  Python을 기준으로 통상 5~15초 가량 시간 소요 (PyPy의 경우 때때로 C언어 보다도 빠르게 동작하기도 함)

▶ 코딩테스트 문제에서 시간제한은 통상 1~5초 가량 (명시돼 있지 않은 경우 통상 5초라고 간주)

 

 

요구사항에 따라 적절한 알고리즘 설계하기

---

▶ 문제에서 시간제한(수행시간 요구사항)을 가장 먼저 확인

 

▶ 시간제한이 1초인 문제를 만났을 때, 일반적인 기준

•  N의 범위가 500인 경우 : 시간복잡도가 O(N^3)인 알고리즘 설계
• N의 범위가 2,000인 경우 : 시간복잡도가 O(N^2)인 알고리즘 설계
• N의 범위가 100,000인 경우 : 시간복잡도가 O(NlogN)인 알고리즘 설계
• N의 범위가 10,000,000인 경우 : 시간복잡도가 O(N)인 알고리즘 설계

 

 

수행 시간 측정 소스코드

---

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

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