바로 이전에 순차 탐색 알고리즘에 대해서 깊게 탐구해보았다. 그러나 평균 시간 복잡도를 좀 더 제대로 확인할 수 있는 방법을 생각해보았다. 내가 구한 공식과 실제 값을 비교해볼 수 있는 프로그램을 구현하는 것이다.
그래서 해당 코드를 직접 수정하여, 예측값과 10000번의 테스트를 통해 얻은 실제 평균값을 비교하는 것이다. 배열 내에 값이 존재할 확률(p)는 50%로 설정해두었다.
구현
#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()
{
int data;
cout << "Enter the number of data : ";
cin >> data;
vector<int> v(data);
for (int i = 0; i < data; i++)
v[i] = i;
int sum = 0;
int loop = 10000;
srand((unsigned int)time(NULL));
for (int i = 0; i < loop; i++)
{
int num = rand() % (data * 2);
int idx = LinearSearch(v, num);
if (idx == -1)
sum += data;
else
sum += idx+1;
}
double expect = (0.5 * data) + (0.5 * ((data + 1)*(data) / ((double)data * 2)));
double count = (double)sum / loop;
cout << "\nExpect : " << expect << "\n";
cout << "Average : " << count << "\n";
return 0;
}
실행결과
예측값과 실제 측정값이 굉장히 유사하다는 것을 확인했다. 테스트 횟수가 10000번이지만 이걸 더욱 더 늘리면 그만큼 더 비슷해질 것이라고 생각한다.
