#3. 순차 탐색 알고리즘 성능 분석

순차 탐색 알고리즘

말 그래도 순차적으로, 정해진 순서에 따라 탐색하는 알고리즘이다.

 

예를 들어 길이가 5인 배열이 존재하고, 이 중 3 이라는 숫자를 찾는다 가정할 때

첫 인덱스부터 마지막 인덱스까지 순차적으로 탐색할 것이다.

 

int LSerach(int ar[], int len, int target)
{
	int i;
	for(i = 0; i<len; i++)
	{
		if(ar[i] == target) return i;
	}
	return -1;
}

ar[] 배열에서 target 과 동일한 인덱스를 찾기 위해 순차적으로 탐색하는 알고리즘이다.

 

이 코드에서 시간 복잡도를 결정할 연산자는 if(ar[i] == target) 의 '==' 가 된다.

Why?

코드의 목적 자체가 target 과 값이 같은지 '확인' 하는 알고리즘이다.

이 확인에서 가장 중요한 연산자가 시간 복잡도를 결정한다.

 

여기서 중심이 되는 연산자의 특징 을 알 수 있는데,

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

라는 것이다.

 

연산자는 총 3개 존재한다 ( i < len / i ++ / ar[i] == target )

여기서 == 연산자가 true 를 반환할 때까지 < 와 ++ 는 계속 수행되기 때문에 의존적이다 라고 말할 수 있다.

 

 

경우 판별

우리가 어떤 가정을 할 때 경우는 최상의 경우, 최악의 경우, 평균적 경우 총 3가지를 따질 수 있는데

성능을 위한 시간 복잡도를 계산할 때는 최악의 경우를 따진다.

Why?

 

최상의 경우 in 순차 탐색 알고리즘

배열의 맨 앞에서 대상을 찾는 경우 가 될 것이다. 이를 Best Case 라고 부르는데,

어떤 방법으로 찾는다고 해도 최상의 결과, 만족스러운 상황이 될 것이기에 연산 횟수가 적다.

따라서 성능 자체의 평가의 주 관심사가 아니다.

 

최악의 경우 in 순차 탐색 알고리즘

배열의 맨 끝에서 대상을 찾거나, 대상이 저장되어 있지 않은 경우가 될 것이다. Worst Case 라고 볼 수 있는데

이 때가 성능 평가의 주 관심사가 될 것이다.

알고리즘 구성에 따라서 탐색의 횟수,

즉 데이터 표본이 많을 수록 소요 시간이 급증할 지, 변화가 없을지 극명하게 나타나기 때문에

최악의 경우를 판단 기준으로 잡는다.

 

 

여기서 한가지 의문으로 최상/최악 만 따질 것이 아니라 평균적인 경우도 따져야 하는게 아닌가 를 들 수 있다.

실제로 일리가 있다고 여겨지는데,

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

 

하지만 실제 적용하기 어려운 이유로

1. 평균적인 경우의 연출이 어려움

2. 이 경우가 평균적인 경우임을 증명하기 어려움

3. 주어진 상황에 따라 결과가 달라짐

이라는 특성 때문이다.

 

특히 3번의 경우는 최악의 경우를 따질 때는 항상 상황이 일정하다 라는 특성과 대비되어 더욱 그렇다.

따라서 평균적인 경우 자체는

계산하기 어렵고, 객관적 평가가 어렵다.

라는 문제점을 가지고 있다.

 

 

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

데이터의 수가 N개 일 때, 최악의 경우의 연산 횟수는 T(n) = N 이 된다

 

 

평균적 경우 시간 복잡도

간단하게 평균적 경우의 시간 복잡도를 계산해볼건데

위에서 말했듯 평균적 경우 자체가 조건이 어렵다.

해서 가정을 두개 추가하고 계산한다.

 

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

2. 배열 첫 요소부터 마지막 요소까지 탐색 대상 존재 확률은 동일하다

 

길이가 7인 배열이 있다고 가정한다.

이 때 모든 요소의 탐색 대상 존재 확률은 동일하므로

첫번째 인덱스의 비교 연산 횟수는 1번이 된다 (맞다 or 틀리다 1회 시행)

두번째 인덱스의 비교 연산 횟수는 2번이 된다 (1번째 인덱스에서 1회 시행 + 2번째 인덱스에서 2회 시행)

 

이렇게 인덱스가 증가함에 따라 비교 연산의 횟수도 증가하며

최종적으로는

길이가 n 인 배열일 때 마지막 인덱스의 비교 연산 횟수 = ( 1 + 2 + ... + n ) 이 될 것이다 : n/2 번

가정에서의 2번에 해당한다.

 

근데 이 n/2 는 데이터가 존재할 때의 확률 이다.

존재하지 않을 확률이 있어 다시 1/2 를 곱해주면 n/4 가 될 것이다.

 

가정 1번은 존재하지 않을 확률 50%, 즉 n/2 가 된다.

 

결론적으로 평균적 경우의 시간 복잡도는 T(n) = n/2 + n/4 = 3n/4 가 된다.

 

 

간단한 가정의 알고리즘임에도 여러 수식이 들어가는 만큼

평균적 경우의 시간 복잡도를 구하기 어렵다는 것을 알 수 있다.