안녕하세요... 과제하다가 밤새서 했는데도 도저히 못찾아내서 질문글 올립니다...ㅠㅠ
#include <iostream>
#include <ctime>
#define ARRAY_SIZE 100
using namespace std;
int my_Binary_Search(int *ary, int x, const int left, const int right)
{
int middle = (left + right) / 2;
if(left <= right)
{
if(x < ary[middle])
{
return my_Binary_Search(ary, x, left, middle - 1);
}
else if(x > ary[middle])
{
return my_Binary_Search(ary, x, middle + 1, right);
}
else
{
return middle;
}
}
return -1;
}
int main()
{
int a[ARRAY_SIZE];
int num;
double time;
double start, end;
int idx;
int i;
for(i = 0; i < ARRAY_SIZE; i++)
{
a[i] = i;
}
cout<<"검색할 숫자를 입력하세요 : ";
cin>>num;
start = clock();
idx = my_Binary_Search(a, num, 0, sizeof(a)/sizeof(int) - 1); // 함수 호출
end = clock();
time = end - start;
if(idx == -1)
{
cout<<"검색에 실패했습니다."<<endl;
}
else
{
cout<<num<<"은 "<<idx + 1<<"번째 인덱스에 저장되어 있습니다"<<endl;
}
cout<<"배열의 크기가 "<<ARRAY_SIZE<<" 일 때 수행시간 : "<<(double)time/CLOCKS_PER_SEC<<endl;
return 0;
}
여기서 매크로 상수의 값을 변화시켜 배열의 크기에 따라 어떤 특정한 수를 찾는데 시간이 얼마나 걸리나를 계산하려고 하는데요...
(예를들어 10, 20, 30, 40, ...100으로 매크로 상수 값을 변화시켜 까지 2라는 수를 찾는데 걸리는 시간)
일단 코드는 이런식으로 짰는데 Visual Studio에서 컴파일했을때는 계속 0만 나오고 우분투환경에서 이클립스로 컴파일 했을떈 매크로상수를 변화시켜도 계속해서 2초라는 같은 수만 나옵니다 ㅠㅠ
혹시나 데이터 타입때문에 그런가 싶어서 double형, long형, float형으로 다 시도해봐도 값은 똑같구요...
대신에 start = clock(); 구문과 end = clock();구문의 위치를 변화시키면 몇 초인지 값이 뜨네요...(제가 하고 싶은건 Binary search함수의 수행시간만 구하고 싶습니다만...) 그런데 제 생각에는 10, 20, 30, 40, ,100으로 변화시키면서 시간이 점점 늘어나야 하는데 10에서 실행했을 때는 0.8초, 100에서 실행했을때는 0.7초 이런식으로 나오기도 하네요...ㅠㅠ
이렇게 계산해서 O(log n)이라는 이론 값과 얼마나 차이가 나나 보려고 하는데 10일때 2초가 나오고, 100일때 1초가 나온다면 이건 이론 값이랑 맞아 떨어지지 않는것 아닌가요!?
밤새 생각해봐도 답이 안나옵니다...ㅠㅠ 질문이 많지만 답변해주시면 감사하겠습니다 오유님들 ㅠㅠ
