알고리즘 성능 평가

복잡도 낮추기

-시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행시간 분석

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

 

python : 통상 5~15초 가량의 시간이 소요됨.

코테에서 시간 제한은 통상 1~5초

시간 제한이 1초인 문제 기준

 

N의 범위	시간 복잡도
500	O(N^3)
2000	O(N^2)
100,000	O(NlogN)
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) #수행 시간 출력