[ 알고리즘 ] 순차 탐색(Linear Search) 이란? 시간 복잡도 계산하기

순차 탐색(Linear Search) 이란? 최악의 경우 시간 복잡도 계산하기

 

순차 탐색이란 말 그대로 맨 앞에서부터 순서대로 탐색을 하는 알고리즘입니다. 

 

 

순차 탐색 알고리즘을 적용한 코드를 보겠습니다. 

※ 윤성우의 열혈 자료구조 책에서 코드 참고하였습니다. 

 

---

 

위의 코드 중 실제로 순차 탐색 알고리즘을 구현하는 부분입니다. 

 

 

for문을 통해 인덱스를 1씩 증가하여 배열를 처음부터 끝까지 목표값과 비교(==)합니다.

그래서 배열(arr)에서 목표값(target)을 찾으면 그 값의 인덱스(i)를 반환합니다. 

 

---

이제 위의 코드를 토대로 시간 복잡도(Time complexity) 를 분석해볼까요?

데이터의 수 n에 대한 연산 횟수의 함수 T(n) 구해봅시다.  

 

연산 횟수라 했으니까 이 알고리즘에서 사용된 연산자 <. ++, ==가 얼마나 수행되는지 알아내면 되겠네요.

그럼 이 중에서 어떤 연산자가 적게 수행되야 좋은 알고리즘일까요?

 

바로 값의 동등을 비교하는 == 연산입니다. 

비교연산의 수행횟수가 줄어들면 < 연산과 ++ 연산의 수행횟수가 줄어들고, 늘어나면 늘어나죠. 

즉, 다른 연산들은 == 연산에 의존적입니다.

 

그래서 == 연산의 횟수를 대상으로 시간 복잡도를 분석하면 됩니다. 

이렇듯 알고리즘의 시간 복잡도를 계산하기 위해서는 핵심이 되는 연산이 무엇인지 잘 판단해야 합니다. 

 

 

---

 

그럼 다시 본론으로 돌아와서 순차 탐색 알고리즘의 비교연산횟수를 계산해봅시다. 

일단 정말 쉽게 생각해볼께요. 

 

순차 탐색은 배열의 첫번째 자리에 있는 값부터 비교했잖아요.

목표값이 아니면 다음 두번째 자리.. 세번째.. 그래도 못 찾으면 네번째.. 다섯...

 

그런데 만약 첫번째 자리에서 바로 목표값을 바로 찾으면 어떻게 돼죠?

뭐 비교 1회만에 원하는 값 찾고 for문을 나오는거죠. 

 

그럼 맨 마지막 자리에서 목표값을 찾으면요?

4회(위의 코드 배열의 크기)만에 찾게 되네요. 

아 물론 목표 값이 없었다면 4회 진행하고 -1 값을 받고요.

 

이렇듯 운이 좋았으면(Best Case, 최선의 경우) 비교 연산 횟수는 1,

안 좋으면(Worst Case, 최악의 경우) 비교 연산 횟수는 n입니다.

(탐색 대상이 되는 요소를 n개로 가정) 

 

---

 

경우마다 연산 횟수가 다른데 어디에 맞춰서 계산해야할까요?

바로 '최악의 경우'입니다.

 

'최상의 경우'는 대부분 긍정적인 결과가 나오고, '최상'과 '최악'의 중간인 '평균적인 경우'를 알아내려고 하면 광범위한 자료들을 수집해야 하기 때문에 알고리즘을 평가하는데 있어서 '최악의 경우'를 가장 많이 따집니다.

여기서는 최악의 경우 순차 탐색 알고리즘의 시간 복잡도를 계산해보면 

위 설명에서 바로 유추할 수 있듯이

 

" 데이터 수가 n개 일 때, 연산 횟수는 n이다. " 

 

즉,

T(n) = n

입니다. 

 

 

 

------------------------------

알고리즘 개념 모아보기 

------------------------------