순차검색(sequential search)

오랜만에 공부관련으로 포스팅하는 것 같다. 좀 게으른 면이 있어서 포스팅은 안했지만 개인적으로 공부는 꾸준히하고 있었다. 잡담은 이 정도로 하고 알고리즘 첫 포스팅을 시작해야겠다.

 

순차 검색이란?(What is sequential search?)

---

순차 검색은 말 그대로 순차적으로 검색하는 방법을 말한다. 이름이 적힌 장부가 하나 있다고 가정해보자. 근데 장부 이름이 정렬이 안되어 있다면 우리는 이름을 찾을 때 처음부터 순차적으로 이름을 찾아야 한다. (찍어서 맞췄다면 축하한다! 당신은 컴퓨터보다 나은 존재다.) 이런 상황에서 순차 검색을 사용한다. 순차 검색은 우리가 가장 쉽게 떠올릴 수 있을 만큼 쉽지만 그만큼 원시적인 방법이라 이후에 나오는 검색 방법에 비해 성능이 상당히 안 좋다. 그럼 순차 검색이 어떻게 생겼는지 확인해보자!

 

순차 검색 알고리즘(sequential search algorithm)

---

void SequentialSearch(int n, const keytype S[], keytype x, index& location)
{
	location = 1;
	while(location <= n && S[location] != x) location++;
	if(location > n) location = 0;
}

자! 위에 소개된 것이 순차 검색 알고리즘이다. 혹시 알고리즘을 그대로 복사하여 과제를 해결하려 했다면 스스로에게 반성하는 시간을 가져보자! 이건 소스코드가 아니라 알고리즘이다. 혹시 알고리즘이 뭔지 모르겠으면 필자의 다른 포스팅을 찾아보길 바란다.

순차 검색

순차 검색은 위와 같이 작동한다. 여기서 n은 배열의 크기, S는 배열, x는 찾는 키값, location은 찾는 키값의 인덱스이다. 이 순차 검색은 원하는 값을 찾으면 location에 인덱스를 반환하고, 없다면 location을 0으로 만든다. 알고리즘에서는 배열이 1부터 시작하기 때문에 0은 없다는 표시를 나타낸다. 그럼 이 알고리즘의 효율을 분석해보자.

 

순차 검색의 최선의 경우(best case of S.R)

---

지금부터 분석하는 알고리즘의 최소 연산 단위는 배열 원소와 x의 비교 즉, while문 안에 조건을 최소 연산 단위로 분석을 시작한다.

순차 검색이 가장 최선인 경우는 당연히 원하는 원소가 가장 앞에 있어 1번에 검색으로 찾을 수 있는 경우이다.

B(n) = 1 ∈O(1)

 

순차 검색의 최악의 경우(Worst case of S.R)

---

 

순차 검색이 가장 최악인 경우는 원하는 원소가 가장 뒤에 있어 n번 검색이 필요한 경우이다.

W(n) = n ∈O(n)

 

순차 검색의 평균의 경우(Average case of S.R)

---

순차 검색이 평균적인 경우는 앞선 분석보단 조금 까다롭다. 

여기서 k는 인덱스의 위치를 의미하기도 하지만 순차 검색에서 인덱스k를 접근했다는 말은 k번의 비교를 한다고 말할 수도 있다. 그러므로 k는 연산 횟수를 의미하기도 한다. 첫 번째 경우는 원소가 반드시 존재한다면 k번째 인덱스에 위치할 확률은 1/n이라는 점을 이용하여 계산을 한다. 두 번째 경우는 배열 안에 있을 수도 있고 없을 수도 있는 상황에서 사용한다. 만약 반드시 존재한다면 첫 번째와 같고 그렇지 않다면 확률을 부여하여 계산을 하게 된다. 배열에 존재하지 않는다면 (1-p)의 확률로 n번의 루프를 돈다. 시간 복잡도는 아래와 같다.

A(n) = (n+1)/2 ∈O(n),  A(n, p) = n(1-p/2) + p/2 ∈O(n(1-p/2))

 

 

순차 검색의 구현(sequential search implementation)

---

여기에 알고리즘 관련 소스코드를 구현해 놓았다.

 

 

GitHub - LimeTree0/Algorithm