알고리즘) 성능평가

알고리즘의 성능평가

• 알고리즘 성능 평가에는 복잡도라는 개념이 사용된다

복잡도

• 계산복잡도 이론에서 나온 것으로 시간 복잡도와 공간 복잡도로 나뉜다

**시간 복잡도

• 알고리즘의 수행 시간 분석
• *공간 복잡도
• 알고리즘의 메모리 사용량 분석

복잡도가 낮을수록 좋은 알고리즘

Big-O 표기법

• 다항식으로 표현된 성능에서 차수가 가장 큰 것만 남기는 것
• 무언가를 무한대로 시행했을때 가장 큰것만 고려해도 크게 차이가 없기 때문에
• 차수가 가장 큰 항만 남기므로
  N^2 + 5N^2 + 100 => O(N^2) 으로 표현

출처: 유튜브 동빈나

제한시간이 1초인 문제일 경우,

N의 범위가 500인 경우 : 최대 시간 복잡도가 O(N^3)

N의 범위가 2000인 경우 : 최대 시간 복잡도가 O(N^2)

N의 범위가 2,000인 경우 : 최대 시간 복잡도가 O(NlogN)

N의 범위가 10,000,000인 경우 : 최대 시간 복잡도가 O(N)

알고리즘 문제 풀이 순서

1. 지문 읽기 / 컴퓨팅 사고

2. 요구사항(복잡도) 분석

3. 문제 해결을 위한 아이디어

4. 소스코드 설계 / 코딩

## 파이썬에서 시간 측정하기
import time
start_time = time.time()
## 소스 코드 
end_time = time.time()
print('time:', end_time - start_time)