순차 탐색(Linear Search) 알고리즘과 시간 복잡도 분석

 

#include <stdio.h>

int LSearch(int ar[], int len, int target) // 순차 탐색 알고리즘 적용된 함수
{
	int i;
	for (i = 0; i < len; i++)
	{
		if (ar[i] == target)
			return i; // 찾은 대상의 인덱스 값 반환
	}
	return -1; // 찾지 못했으면 -1 반환
}

int main(void) {
	int idx;
	int arr[] = { 3, 5, 2, 4 ,9 };

	idx = LSearch(arr, sizeof(arr) / sizeof(int), 4);

	if (idx == -1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스 : %d \n", idx);

	idx = LSearch(arr, sizeof(arr) / sizeof(int), 7);

	if (idx == -1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	return 0;
}

맨 앞에서 순서대로 탐색을 진행하는 알고리즘이기에 순차 탐색이라는 이름이 붙었습니다.

 

그 중 실제로 탐색을 하는 코드만 별도로 보겠습니다.

for(i = 0; i < len; i++){
	if(ar[i] == target)
    	return i; // 찾은 대상의 인덱스 값 반환
}

위 코드에서 시간 복잡도에 크게 좌지우지 되는 값은 '==' 입니다. 왜냐면 비교연산의 수행횟수가 줄어들면 '<' 연산과 '++' 연산의 수행ㅅ=횟수도 줄어들기 때문입니다.

 

위 탐색 알고리즘에서 운이 좋으면 수행 횟수 한 번에 찾을 수 있을 것이고, 운이 없으면 맨 마지막에 저장되어 있거나 찾거나 하는 값이 없는 경우에 비교연산의 수행횟수는 n이 됩니다.

 

그런데 우리는 'worst case'만 고려할 것입니다. 왜 평균이 아닐까요?? 평균을 하려면 다양한 이론이 적용되고, 분석에 필요한 여러가지 시나리오가 필요하기 때문에 쉽지 않습니다.

---

최악의 케이스를 생각하기

사실 계산할 것이 없습니다. 왜냐면

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

 

그래서 T(n) = n입니다.

---

평균적인 경우

평균적인 가정을 위한 가정을 두 가지를 해보겠습니다.

1. 탐색 대상이 배열에 존재하지 않을 확률을 50%라고 가정합니다.
2. 배열의 첫 요소부터 마지막 요소까지, 탐색 대상이 존재할 확률은 동일합니다.

우선 탐색 대상이 존재하지 않는 경우엔 총 n번의 비교연산을 진행해야 합니다. 

그럼 나머지 50%의 확률에 해당하는, 탐색 대상이 존재하는 경우의 연산횟수를 계산해보면 n/2 입니다.

 

사실 정확히 n/2가 아닙니다. 하지만 이 경우엔 근사치 계산을 합니다. 그래서 이 둘을 50%로 나눠서 더하면 T(n) = (3/4)*n 입니다.

 

최악의 케이스와 평균적인 경우 두 가지를 나눠서 생각해봤는데 사실 평균적인 경우에서 했던 가정들은 신뢰를 크게 하지 못하기 때문에 '최악의 경우'를 시간 복잡도의 기준으로 삼는 이유입니다.

---

이상 순차 탐색(Linear Search) 알고리즘과 시간 복잡도 분석 였습니다. ^_^