1_3 자료구조와 알고리즘의 이해

※ 알고리즘의 성능 분석 방법

 

순차 탐색 알고리즘 적용된 함수

 

1. 중심이 되는 연산자 ( == )

2. 주변 연산자 ( <, ++ )

 

* 주변 연산자의 연산횟수는 중심이 되는 연산자의 연산 횟수에 의존한다.

 

 

※ 최악의 경우와 최상의 경우

 1) 순차 탐색 상황 하나 : ( 운이 좋은 경우 )

 - 배열의 맨 앞에서 대상을 찾는 경우

 - 만족스러운 상황이므로 성능평가의 주 관심이 아니다!

 - '최상의 경우(base case)' 라고 한다.

    T(n) = 1

* 시간 복잡도, 공간 복잡도 각각에 대해서 최악의 경우와 최상의 경우를 구할 수 있다.

 

 2) 순차 탐색 상황 둘 : ( 운이 좋지 않은 경우 )  

- 배열의 끝에서 찾거나 대상이 저장되지 않은 경우

- 만족스럽지 못한 상황이므로 성능평가의 주 관심이다!

- 최악의 경우 (worst case) 라고 한다. 

   T(n) = n

 

 

※ 평균적인 경우(Average Case)

 1) 가장 현실적인 경우에 해당한다.

 - 일반적으로 등장하는 상황에 대한 경우의 수 이다.

 - 최상의 경우와 달리 알고리즘 평가에 도움이 된다.

 - 하지만 게산하기가 어렵고 객관적 평가가 쉽지않다.

 

2) 평균적인 경우의 복잡도 계산이 어려운 이유

 - '평균적인 경우'의 연출이 어렵다

 - '평균적인 경우'임을 증명하기 어렵다.

 - '평균적인 경우'는 상황에 따라 달라진다.

 

* 반면 최악의 경우는 늘 동일하다.

 

 

※ 순차 탐색 최악의 경우 시간 복잡도

- 데이터의 수가 n개 일때, 최악의 경우에 해당하는 연산횟수는(비교연산의 횟수는) n이다.

=> T(n) = n    -> 최악의 경우를 대상으로 정의한 함수 T(n)