열혈 자료구조 - 1-2. 알고리즘의 성능 분석 방법(2)

순차 탐색 알고리즘의 시간 복잡도

- 순차 탐색 알고리즘 : 배열안에 원하는 요소를 찾을 때 첫번째 요소부터 마지막 요소까지 순차적으로 찾아가는 탐색 방법

- 중심이 되는 연산 : '==' (탐색이기 때문에 확인하는 것이 중심)

int LSearch(int arr[], int len, int target)
{
  int i;
  for(i = 0; i < len; i++) {
    if(arr[i] == target)	return i;	// 찾은 대상의 인덱스 값 반환
  }
  return -1;		// 없으면 -1 반환
}

- 시간 복잡도를 구하기 위해 T(n)을 구해야 함

   -> T(n)을 구하기 위해 최상의 경우, 최악의 경우를 구해야 함

   -> 최상의 경우(best case) : 순차 탐색에서 첫번째 인덱스에서 대상을 찾는 경우, T(n) = 1

   -> 최악의 경우(worst case) : 순차 탐색에서 마지막 인덱스에서 대상을 찾는 경우, T(n) = n(배열의 길이)

   -> T(n)은 최악의 경우를 기준으로 함

   -> 최악의 경우같이 극단적인 경우를 기준으로 하는 것보다 평균적인 경우를 두고 기준을 둬야 하지 않냐고 말할 수 있음

   -> 하지만 평균적이라는 것은 객관적이지 않고 상황에 따라 달라질 수 있음

 

- 순차탐색 알고리즘의 평균적인 경우

   -> 평균적인 경우를 구하기 위해서는 가정이 필요

   -> 가정1. 탐색 대상이 배열에 존재하지 않을 확률이 50%

   -> 가정2. 배열의 첫 요소부터 마지막 요소까지 탐색 대상이 존재할 확률이 동일 = 찾을 대상이 배열의 어떤 인덱스여도 발견될 확률이 동일

   -> 찾으려는 대상이 가장 처음에 있다면 비교 연산을 1번하지만 마지막에 있다면 n번을 진행해야 함

   -> 결국 데이터를 찾기 위해서 평균적으로 n/2 번 연산을 진행해야 함

   -> 결론적으로 T(n) = n * 1/2 (탐색 대상이 존재하지 않는 경우) + n/2 * 1/2 (탐색 대상이 존재하는 경우)