분석

시간복잡도 분석 (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)