4. do it! 03-1 검색 (선형, 이진) ,복잡도 - C언어

최근 교재 두개를 가지고 공부하다보니 공부할때 겹쳐지는 챕터는 두 교재 모두 다른 방식으로 설명하기 때문에 더 이해가 되서 좋다.

 

용도나 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘을 선택해야 합니다.

 

선형 검색 (순차 검색)

무작위로 늘어놓은 데이터 모임에서 검색을 수행합니다.

원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색

ex) a[0] 과 원하는 키 비교 -> 틀림 -> a[1]과 키 비교 -> 틀림 -> a[3]과 비교

 

이때 종료조건이

1. 배열이 끝을 지나간 경우
2. 검색할 값과 같은 요소를 발견 한 경우

이렇게 두가지를 가지게 되는데 이 종료조건을 검사하는 비용도 만만치 않기 때문에 이를 해결하는 방법으로 보초법(sentonel method)이 있다.

보초법이란 배열의 마지막에 검색할 값을 넣어 검색이 맨 마지막에 성공할 경우 -1을 출력할 수 있는 방법이다.

int a[n+1]=key; //배열의 마지막에 찾을 값 넣기
for(i=0;i<n+1;i++){
	if(a[i]==key)
    	break;
    }
return i==n? -1:i; //배열이 마지막까지 갔을 경우를 판단

이런식으로 작동하게 되면 종료판단이 하나로 줄어들기 때문에 검사비용을 효과적으로 줄일 수 있다.

 

 

이진 검색

일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행합니다.

검색 대상이(배열) 정렬되어 있음을 가정 가운데 인덱스를 원하는 키 값과 비교해 범위를 줄여나가는 검색

ex) a[10]중 a[5]의 값과 원하는 키 비교 -> 키값이 큼-> a[7]과 키 값 비교

#include <stdio.h>
int search(int a[], int n, int key){
    int first =0; //검색범위 맨 앞의 인덱스
    int last =n-1; //검색범의 맨 뒤의 인덱스
    int mid;
    do{
        mid = (first+last)/2; //검색범위의 중간 값 구하기
        if(a[mid]==key) //검색값과 같으면 반환
            return mid;
        else if(a[mid]<key) //중앙값이 검색 값보다 작으면
            first = mid +1; //검색범위 앞의 값 조정
        else
            last = mid-1; //중앙값이 검색값보다 크면 뒷 검색범위 조정
    } while(first<=last); //첫번째 인덱스값이 마지막 인덱스값보다 커질때까지 반복(검색범위가 초과가되면 탈출)
    return -1;            //검색이 안됐으면 -1 반환
}
int main(){
    int i,nx, ky, idx;
    scanf("%d", &nx); //배열개수
    int x[nx];
    for(i=0;i<nx;i++){  //오름차순으로 입력
        scanf("%d",&x[i]);
    }
    printf("검색 값\n");
    scanf("%d",&ky);
    idx=search(x,nx,ky);
    if(idx==-1)
        printf("검색에 실패했습니다\n");
    else
        printf("%d은 x[%d]에 있습니다.", ky, idx);
}

 

복잡도

1. 시간 복잡도 - 실행에 필요한 시간을 평가한 것
2. 공간 복잡도 - 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

n만큼 반복되는 횟수를 O(n)라고 표시해보자. (O은 Order에서 가져옴)

선형검색의 시간 복잡도

int i =0;               //O(1)
	while(i<n){     //O(n)
    	if(a[i] == key) //O(n)
       	    return i;   //O(1)
        i++;            //O(n)
    }
return -1;              //O(1)

O(1) + O(n) + O(n) + O(1) + O(n) + O(1) =O(max( 1, n, n, 1, n, 1)) = O(n)

*max(a, b)은 a와 b가운데 큰쪽을 나타내는 함수

 

이진 검색의 시간복잡도

O(1) + O(1) + O(log n) + O(1) + O(log n) + O(1) =O(max( 1, 1, log n, 1, logn n, 1)) = O(log n)