순차 탐색 알고리즘은 탐색 알고리즘의 하나다.
다양한 알고리즘들 중에서도 가장 간단한 알고리즘이라고 할 수 있다. 먼저 벡터와 함수를 활용하여 코드를 구현해보자.
구현
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
using namespace std;
int LinearSearch(vector<int> x, int target)
{
for (int i = 0; i < x.size(); i++)
if (x[i] == target)
return i;
return -1;
}
int main()
{
vector<int> v(10);
for (int i = 0; i < 10; i++)
{
v[i] = i;
cout << "v[" << i << "] = " << v[i] << "\n";
}
cout << "\nSearch : ";
int num;
cin >> num;
int idx = LinearSearch(v, num);
if (idx == -1)
cout << "Search Failed : No value";
else
cout << "Target Index : v[" << idx << "]\n";
return 0;
}
실행결과
0~9 사이의 값을 가진 벡터 중에서 해당 값(target)이 어느 위치(idx)에 위치하는지 출력한다.
벡터 내에서 값을 발견하면 해당 위치 값을 return 하지만, 값이 존재하지 않으면 -1을 return 한다.
시간 복잡도
시간 복잡도는 3가지로 나눌 수 있다. 최선(best), 최악(worst), 평균(average)의 경우다.
순차 탐색 알고리즘의 시간 복잡도를 따지 이전에, 함수 내부에서 행해지는 비교연산(==)이 핵심 연산임을 알아야 한다. 비교연산이 줄어들면 자연스럽게 for문의 다른 연산들(<, ++)도 줄어들기 때문이다. 그렇다면 이제부터 3가지 시간복잡도를 하나씩 순서대로 알아보자. 모든 설명은 위의 구현된 코드에 기반한다.
<!-- 더보기 버튼 클릭 -->
1. 최선의 경우 (Best case)
입력값을 0으로 넣은 경우다. 넣자마자 값을 발견하게 되므로 비교 연산 횟수는 단 한 번이다.
∴ B(10) = 1
2. 최악의 경우 (Worst case)
입력값을 9, 또는 0~9 이외의 값으로 넣은 경우다. v[0]부터 v[9] 모두 탐색하게 된다.
∴ W(10) = 10
3. 평균적인 경우 (Average case)
평균적인 경우의 시간 복잡도를 계산하기 위해서는 2가지의 가정이 필요하다.
첫째로는, 탐색 대상이 존재할 확률에 대한 가정. 둘째, 각 배열에 탐색 대상이 존재할 확률이다. 그래서 다음과 같이 가정한다.
1. 탐색 대상이 배열 내에 없을 확률은 50%다.
2. 탐색 대상이 존재할 확률은 모든 배열의 각 요소마다 동일하다.
먼저 탐색 대상이 배열에 없는 경우를 생각해보자. 이 경우의 연산 횟수는 위에서 이미 알아본 바와 같이 최악의 경우의 횟수인 10이다.
반대로 탐색 대상이 배열에 존재하는 경우를 생각해보자. 1번 탐색하는 경우부터 10번 탐색하는 경우까지 많지만 이를 평균 내보면 (1부터 10까지의 합) / (경우의 수 : 10) = 5.5가 될 것이다. 얼추 10/2라고 생각할 수도 있겠다.
∴ A(10) = (0.5 * 10) + (0.5 * 5.5) = 7.75
그렇다면 이것을 직접 코드로 구현하여 검증해보자.
구현
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
int LinearSearch(vector<int> x, int target)
{
for (int i = 0; i < x.size(); i++)
if (x[i] == target)
return i;
return -1;
}
int main()
{
vector<int> v(10);
for (int i = 0; i < 10; i++)
{
v[i] = i;
cout << "v[" << i << "] = " << v[i] << "\n";
}
int sum = 0;
int loop = 10000;
srand((unsigned int)time(NULL));
for (int i = 0; i < loop; i++)
{
int num = rand() % 20;
int idx = LinearSearch(v, num);
if (idx == -1)
sum += 10;
else
sum += idx+1;
}
double count = (double)sum / loop;
cout << "\nAverage : " << count << "\n";
return 0;
}
코드 설명
우선 찾고자 하는 값은 0~19 사이에서 랜덤으로 지정된다. 가정 1을 충족시키기 위해서다. 그리고 loop(10000) 만큼 반복해서 순차 탐색을 진행하고 그때마다 연산 횟수를 모두 더하고 마지막에 연산 횟수의 평균을 구하는 것이다.
실행결과
결론
나는 모든 경우의 데이터 크기를 10으로 한정해두었다. 그렇다면 데이터 크기를 n이라는 변수로 두었을 때의 시간 복잡도도 알아보자.
B(n) = 1 // 이는 어느 경우든지 동일한 상수 1이 된다.
W(n) = n // 데이터 크기만큼 탐색한다.
그러나 평균적인 경우를 식으로 만들려면 그 모양이 깔끔하진 않다. 수학 기호들이 필요한데 컴퓨터로 쓰긴 귀찮으니 자필로 대체한다.
위의 예시 코드에서 몇 가지만 조금 손보면, 데이터 크기 n에 대한 평균인 경우의 값도 구할 수 있을 것이다. 벡터 선언 부분이랑 랜덤 값 범위랑 탐색 범위 벗어난 경우 합에 대한 값 3가지 정도.
블로그를 오픈하고 처음 쓰는 글이지만 이게 누군가에게는 조금의 도움이 되었길 바란다.
