순차 탐색, 이진 탐색 시간복잡도

2019.01.01.

 

속도에 해당하는 알고리즘의 수행시간을 분석결과를 시간복잡도

메모리 사용량에 대한 분석결과를 공간복잡도 라고 한다고 한다.

 

시간복잡도의 경우 최악의 경우를 기준으로 발생하는 연산의 횟수 라고 한다.

 

#define _CRT_SECURE_NO_WARNINGS   
#include <stdio.h>  
 
int Findnum(int arr[], int len, int target);
 
int main()
{
    int arr[] = {1, 2 , 3, 4, 5};
    int idx;
    int num;
 
    scanf("%d", &num);
 
    idx = Findnum(arr, sizeof(arr) / sizeof(int), num);
 
    if (idx == -1)
    {
        printf("숫자가 없습니다");
    }
    else
    {
        printf("숫자가 있습니다");
    }
 
    return 0;
}
 
int Findnum(int arr[] , int len, int target)
{
    for (int i = 0;i < len;i++)
    {
        if (arr[i] == target)
            return i;
    }
    return -1;
}
 

다음은 간단한 순차탐색 알고리즘 입니다.

 

수를 입력하면 1-5 중에 있는지 순서대로 확인하고 없으면 -1을 있으면 그 숫자가 몇번째 배열에 있는지 출력한다.

 

위 함수의 시간복잡도를 구해보자면 1일 경우 1번째 배열만 검색 하면 되니 연산 횟수는 1이다.

최악의 경우 배열의 n의 크기 일때, n번째 수를 검색하면 연산횟수가 n이 되니 시간복잡도는 n임을 쉽게 구할 수 있다.

 

 

 

그리고 위의 순차 탐색보다 이진 탐색이 성능이 좋다고 합니다.

먼저 배열에 저장된 데이터가 정렬되어 있어야 한다는 조건이 필요합니다.

 

이진탐색은 양 끝 배열index를 합해서 절반으로 나눈값의 index를 확인해 봅니다.

만약 찾는 숫자가 없을 경우 저장된 숫자가 찾는 숫자보다 큰지 작은지를 비교한후 

작을경우 처음값과 중간값 index를 처음과 같은 방법으로 비교 

클 경우 중간값과 끝깞 index를 처음과 같이 비교하는방법으로

탐색하는 크기를 절반씩 줄여나가는 것입니다.

 

이를 코드로 구현하자면 

#define _CRT_SECURE_NO_WARNINGS   
#include <stdio.h>  
 
int Findnum(int arr[], int len, int target);
 
int main()
{
    int arr[] = {1, 2 , 3, 4, 5};
    int idx;
    int num;
 
    scanf("%d", &num);
 
    idx = Findnum(arr, sizeof(arr) / sizeof(int), num);
 
    if (idx == -1)
    {
        printf("숫자가 없습니다");
    }
    else
    {
        printf("%d번째에 숫자가 있습니다", idx+1);
    }
 
    return 0;
}
 
int Findnum(int arr[] , int len, int target)
{
    int first = 0;
    int last = len - 1;
    int mid;
 
    while (first <= last)
    {
        mid = (first + last) / 2;
 
        if (target == arr[mid])
        {
            return mid;
        }
        else
        {
            if (target < arr[mid])
                last = mid - 1;
            else
                first = mid + 1;
        }
    }
    return -1;
    
}

 

main함수는 같고 Findnum함수만 바뀌었습니다.

 

위 함수의 시간복잡도를 구해보자면 데이터를 n개로 주어졌을때

n을 2로 나누는것을 1이 될때까지 k번 실행하고 데이터가 1개 남았을때 1회 실행한다.

즉 시간복잡도 함수는 k+1이다.

 

k를 구해보자면 

 

 

 

결과적으로 시간 복잡도는 

이다

 

뒤에 +1을 생략하는 이유는 한없이 커지는 n에 비해 1은 큰 변화를 주지 않기 때문이다.

 

참고: 윤성우의 열혈 자료구조