알고리즘 성능 평가

빅오 표기법(Big-O Notation)

• 가장 빠르게 증가하는 항만을 고려하는 표기법
• 함수의 상한만을 나타내게 됨
• ex)3n^3+5n^2+1,000,000인 알고리즘 -> O(N^3)차수가 가장 큰 항만을 남기기 때문에

순위	명칭
O(1)	상수시간
O(logN)	로그시간
O(N)	선형시간
O(NlogN)	로그 선형 시간
O(N^2)	이차시간
O(N^3)	삼차시간
O(2^N)	지수시간

상수 시간으로 갈 수록 좋음

 

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

• 문제에서 시간제한(수행시간 요구사항)을 가장 먼저 확인
• 시간제한이 1초인 문제일때,

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