-
시간복잡도 분석 (time complexity analysis)
알고리즘의 실행시간(running time) 효율성 분석
- 알고리즘의 실제 실행시간을 측정하는 방법 : 실행환경의 영향을 많이 받음
- 시간복잡도 분석은 물리적 시간 대신 명령문의 실행 횟수를 분석
- 주어진 알고리즘의 실행시간은 입력(input)에 따라 달라짐
입력 크기 : 흔히 n으로 표현한다.
시간복잡도 분석
모든 경우 시간복잡도 T(n)
최악의 경우 시간복잡도 W(n) : 최대 실행 횟수
평균의 경우 시간복잡도 A(n) : 평균 실행 횟수최선의 경우 시간복잡도 B(n) : 최소 실행 횟수
빅오 표기법
- 정확한 실행 횟수보다 n이 커짐에 따라 어떤 비율로 시간이 증가하는지가 중요
- 입력 크기 n과 상관없이 상수 번 실행되는 명령문은 무시해도 됨
- n에 의존하는 항이 여러 개인 경우, 가장 값이 높게 올라갈 항이 전체 시간을 지배한다
==> 시간이 중요하다
빅오 표기법 분석 방법
1) 입력크기 파악
2) 일력(내용)에 따라 시간이 달라지는지>
3) 실행시간에 영향을 주는 연산의 실행 횟수 ex) T(n) = n+3
4) 빅오표기법을 사용하여 시간복잡도(의 차수) ex) T(n) = O(n)