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

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

시간복잡도의 2가지중 한가지가 바로 순차탐색 알고리즘이다.

순차 탐색 알고리즘은 맨 앞에서부터 순서대로 탐색을 진행하는 알고리즘이기에

순차 탐색 알고리즘이라고 부른다.

ex)

for(i=0 ; i<len ; i++) {

if(arr[i] == target)

return i;    //    찾은 대상의 인덱스 값 반환

}

이러한 예제중에서 시간복잡도로 평가하기 위해선

연산의 횟수를 세어서 평가해야하는데 알고리즘에 사용된 연산자는 <, ++, ==

이렇게 3개가 있다.

하지만 연산이 3개가 있다고 연산의 횟수를 3이라고 하면안된다.

왜냐하면 연산중에서도 중심이 되는 특정 연산을 찾아내서 세어야 하기 때문이다.

그렇다면 중심이 되는 특정 연산은 무엇인가?

알고리즘을 잘 보면 어떠한 특정 연산에 의해 다른 연산자들이 의존한다.

잘 보면 == 의 연산횟수가 줄어들수록 <<와 ++의 연산횟수들이 줄어드는 경우를 볼 수있다.

예제의 알고리즘에서 보면 == 이 연산자에 의해 다른 <<와 ++의 연산자들이 의존적임을 알 수있다.

그래서 중심이 되는 특정 연산자는 바로 == 연산자이다.

특정한 연산자를 찾는건 아직 익숙치 않지만 차차 연습하면 알아낼 수 있다.

최선의 경우(Best Case) 최악의 경우(Worst Case) 평균적인 경우(Average Case)

알고리즘의 비교연산횟수를 계산해보려면 경우의 수가 필요하다는걸 알수있다.

예를들어 알고리즘의 찾고자 하는 값이 배열의 맨앞인경우 

수행횟수 1번째에 찾아서 최선의 경우가 될 것이다.

하지만 배열의 맨 마지막인 경우와 찾고자 하는 값이 없을경우는 최악의 경우가 될 것이다.

최선의 경우(Best Case)

알고리즘을 평가하는데 있어서 최선의 경우를 두고 평가를 하지않는다. 

최선의 경우일때는 데이터가 무수히 많아도 1번의 연산횟수에 끝이 나기때문에

식을 구하면 T(n) = 1 이된다.

즉, 최선의 경우는 관심밖이다.

최악의 경우(Worst Case) 

알고리즘은 최악의 경우를 두고 평가를 한다. 

왜냐하면 최악의 경우는 늘 동일하기 때문이다.

최악의 경우는 데이터의 수가 n개일 때 연산횟수는 n이다.

앞서 블로그에 있던 공식을 대입하면 T(n) = n 으로 함수시킬 수 있다.

평균적인 경우(Average Case)

평균적인 경우는 가장 현실적이지만 계산하기가 어렵고 객관적인 평가가 쉽지않다.

게다가 평균적인 경우의 연출이 어렵고, 평균적인 경우임을 증명하기가 어렵고, 

평균적인 경우는 상황에 따라 달라지기때문에 복잡도 계산이 어렵다.

그럼에 도 평균적인걸 구하기 위해선 2가지의 가정이 필요하다.

이 가정들을 공식화 하면

탐색 대상이 존재하지 않는 경우의 연산횟수를 n이라 하고

가정2에 의해서 탐색 대상이 존재하는 경우의 연산횟수는 n/2 이라한다.

일단 배열 탐색대상이 존재할 경우와 존재하지않을 경우를 나눠서 연산횟수를 구해보자

1) 존재하지 않을경우

일단 존재하지않을때에는 데이터의 갯수가 n개일 때, 

총 n번을 비교연산 진행해야한다.

n번까지 진행을 해야 마지막으로 데이터가 존재하지않는다고 판단하기때문이다.

그래서 존재하지않는 경우의 연산횟수는 n

2) 존재할 경우

존재할 경우를 이해시키기위해 예제를 마련하겠다.

길이가 7인 배열에 첫번째의 존재할 경우 비교연산의 수는 1번, 

두번째에 존재할 경우 2번,

세번째에 존재할 경우 3번,

.

.

.

이렇게 게속 가면 7번째의 존재할 경우는 7번이 되어 평균적으로 n/2임을 알수있다.

하지만 정확이 계산을 해보면 n/2는 아니게 된다. 하지만 이 경우는 근사치를 계산해서

수식의 간결해지고 배열의 길이가 길어질수록 근사치 계산결과에 더 가까워지기 때문이다.

즉, 이렇게 존재하지않을 경우와 존재할 경우를 구했으니 둘다 더하면 n + n/2구나 하겠지만

가정1에 의해서 존재할 경우와 존재하지 않을 경우가 50% 이기 때문에 n * 50% + n/2 * 50%

를 해주어야 한다. 이를 식으로 묶어두면 다음과 같이 나온다.

즉 T(n) = 3/4n 이 평균적인 경우의 시간 복잡도 이다.

하지만 앞서 말했듯이 평균적인 경우를 구하기 위해선 뒷받침할 근거가 부족하기때문에 

신뢰도가 낮아 최악의 경우를 시간복잡도의 기준으로 삼는다.