[알고리즘] 선형 검색

선형 검색

배열에서 검색하는 방법 가운데 가장 기본적인 알고리즘.

요소가 직선 모양으로 늘어선 배열같은 자료구조에서 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞에서부터 순서대로 요소를 검색하는 알고리즘.

 

기본 종료 조건

1. 검색할 값을 발견하지 못하고 자료의 끝을 지나간 경우

2. 검색할 값과 같은 요소를 발견한 경우

// 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형 검색
int search(const int a[], int n, int key) {
    int i = 0;
    while(1) {
        if(i ==n)
            return -1; // 검색 실패
        if(a[i] == key)
            return i; // 검색 성공
        i++;
    }
}

 

보초법

검색하기 전에 검색하고자 하는 키 값을 보초로써 맨 끝 요소에 저장시켜놓음.

보초법을 사용하면 위 종료 조건의 비용을 반으로 줄일 수 있다.

// 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 선형 검색(보초법)
int search(int a[], int n, int key) {
    int i = 0;
    a[n] = key; // 참고로 배열이 n+1크기만큼 할당되어있어야한다.
    while(1) {
        if(a[i] == key)
            return i;
        i++;
    }
    return i == n ? -1 : i;
}

 

 

분석

선형 검색의 평균 횟수 : N/2회

시간복잡도 : O(n)

-> n에 비례하는 횟수만큼 실행하는 경우엔 O(n)이라고 간단히 표현한다. O(n/2)가 아닌 O(n)으로 표현하는 이유는 n의 값이 무한히 커진다고 가정했을때 그 값의 차이가 무의미해지기 때문이다.

 

2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 가장 높은 복잡도를 선택한다.

즉 위에서 기본 종료 조건이 두개일 때에도 시간복잡도가 O(n) + O(n) = O(n)이고, 보초법을 사용하여 기본 종료 조건이 한개일 때에도 시간복잡도가 O(n)이다. ( 물론 실제로 두 프로그램의 효율상 차이는 있겠지만 시간복잡도의 표현은 이렇게 한다. )

 

+ 시간복잡도 계산은 극한의 개념을 도입한다.