순차 탐색과 이진 탐색 알고리즘 성능 비교 [C++소스]

순차 탐색과 이진 탐색 알고리즘 성능 비교 [C++소스]

---

Program.cpp

"본문 내용"은 언제나 휴일 본 사이트에 있습니다.

---

#include <iostream>

#include <string>

#include <time.h>

#include <stdlib.h>

using namespace std;

 

int *sequentailsearch(int *base, size_t n, int value)

{

    for(size_t s = 0; s<n; s++)

    {

        if(base[s] == value)

        {

            return base+s;

        }

    }

    return 0;

}

 

int *binarysearch(int *base, size_t n, int value)

{

    if(n<=0)

    {

        return 0;

    }

    int gap = base[n/2] - value;

    if(gap == 0)

    {

        return base + n/2;

    }

    if(gap>0)

    {

        return binarysearch(base,n/2,value);

    }

    return binarysearch(base+n/2+1, n-n/2,value);

}

 

int main()

{

    int arr[100000];

    srand((unsigned)time(0));//랜덤 시드 값 설정

 

    for(int i = 0; i<100000;i++)

    {

        arr[i] = i*5+rand()%5;

    }

       

    clock_t st,et;

    st = clock();

    for(int tc = 0; tc<10000; tc++)

    {

        int index = rand()%100;       

        sequentailsearch(arr,100,arr[index]);

    }

    et = clock();

    cout<<"100개에서 순차 탐색으로 10000번 수행에 걸린 시간:"<<et-st<<endl;

 

    st = clock();

    for(int tc = 0; tc<10000; tc++)

    {

        int index = rand()%100000;       

        sequentailsearch(arr,100000,arr[index]);

    }

    et = clock();

    cout<<"10만개 순차 탐색으로 10000번 수행에 걸린 시간:"<<et-st<<endl;

 

    st = clock();

    for(int tc = 0; tc<10000; tc++)

    {

        int index = rand()%100;       

        binarysearch(arr,100,arr[index]);

    }

    et = clock();

    cout<<"100개에서 이진 탐색으로 10000번 수행에 걸린 시간:"<<et-st<<endl;

 

    st = clock();

    for(int tc = 0; tc<10000; tc++)

    {

        int index = rand()%100000;       

        binarysearch(arr,100000,arr[index]);

    }

    et = clock();

    cout<<"10만개에서 이진 탐색으로 10000번 수행에 걸린 시간:"<<et-st<<endl;

   

    return 0;

}

▷ 실행 결과

100 개에서 순차 탐색으로 10000번 수행에 걸린 시간:3

10만 개 순차 탐색으로 10000번 수행에 걸린 시간:782

100 개에서 이진 탐색으로 10000번 수행에 걸린 시간:4

10만 개에서 이진 탐색으로 10000번 수행에 걸린 시간:10

---

프로그래밍 언어 및 기술 학습, 무료 동영상 강의 언제나 휴일