코딩테스트 준비 - 알고리즘 성능 평가

복잡도란?

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

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

 

시간 복잡도가 높다 -> 알고리즘 실행에 오랜 시간이 걸린다

공간 복잡도가 높다 -> 알고리즘 실행에 많은 메모리가 사용된다

 

 

빅오 표기법

가장 빠르게 증가하는 항만 고려하는 표기법

ex) 연산 횟수가 3N^3 + 5N^2 + 1,000,000 이면 시간 복잡도는 O(N^3)

 

 

 

알고리즘 설계 팁

연산 횟수가 5억을 넘어가는 경우:

- C언어: 1~3초 가량 시간 소요

- Python: 5~15초 가량 시간 소요

 

코딩테스트 문제에서 시간제한은 통상 1~5초 가량

 

 

수행 시간 측정 소스코드 예제

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

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