kingsubin

- 선형 검색

요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하면 되는데,

이를 선형 검색(linear search) 또는 순차 검색 (sequential search) 이라는 알고리즘이다.

 

배열 검색의 종료 조건)

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

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

 

선형 검색은 배열에서 순서대로 검색하는 유일한 방법이다.

 

선형 검색은 반복할 때마다 종료 조건 1,2 를 모두 판단한다. 

단순한 판단이라고 생각할 수 있지만 종료 조건을 검사하는 비용은 결코 무시할 수 없다.

이 비용을 반으로 줄이는 방법이 보초법 (sentinel method)이다.

 

검색하기 전에 검색하고자 하는 키 값을 맨 끝 요소에 저장한다.

이때 저장하는 값을 보초(sentinel)이라고 한다.

이렇게 하면 원하는 키 값을 찾지 못했을 때를 판단하는 종료 조건이 없어도 된다.

보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 한다.

 

// 선형검색
public class Ex1 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("요솟수 : ");
        int num = scanner.nextInt();
        int[] x = new int[num+1];

        for (int i = 0; i < num; i++) {
            System.out.print("x[" + i + "] : ");
            x[i] = scanner.nextInt();
        }

        System.out.print("검색할 값 : ");
        int key = scanner.nextInt();
        int idx = seqSearch(x, num, key);

        if (idx == -1) {
            System.out.println("그 값의 요소는 없습니다");
        } else {
            System.out.println(key + "는 x[" + idx + "]에 있습니다. ");
        }
    }

    // 요솟수가 n인 배열 a에서 key와 같은 요소를 선형 검색합니다.(보초법 추가)
    static int seqSearch(int[] a, int n, int key) {
        int i = 0;

        a[n] = key;

        while (true) {
            if (a[i] == key){
                break;
            }
            i++;
        }

        return i == n ? -1 : 1;
    }
}

 

---

- 이진 검색

이 알고리즘을 적용하는 전제 조건은 데이터가 키 값으로 이미 정렬(sort) 되어 있다는 것이다.

이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다는 장점이 있다.

 

이진 검색(binary search) 은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.

 

n개의 요소가 오름차순으로 늘어선 배열 a에서 키를 이진 검색으로 검색하는 과정을 일반적인 방법으로 표현하면

맨 앞 인덱스를 pl, 맨 끝 인덱스를 pr, 중앙 인덱스를 pc라고 지정한다.

pl = 0, pr = n-1, pc = (n-1) / 2이다.

 

종료 조건)

1. a[pc]와 key가 일치하는 경우

2. 검색 범위가 더 이상 없는 경우

 

// 이진검색
public class Ex4 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("요솟수 : ");
        int num = scanner.nextInt();
        int[] x = new int[num];

        System.out.println("오름차순으로 입력하세요 . ");

        System.out.print("x[0] : ");
        x[0] = scanner.nextInt();

        for (int i = 1; i < num; i++) {
            do {
                System.out.print("x[" + i + "] : ");
                x[i] = scanner.nextInt();
            } while (x[i] < x[i-1]);
        }

        System.out.print("검색할 값 : ");
        int key = scanner.nextInt();

        int idx = binSearch(x, num, key);
        if (idx == -1) {
            System.out.println("그 값의 요소가 없습니다.");
        } else {
            System.out.println(key + "는 x[" + idx + "]에 있다.");
        }
    }

    static int binSearch(int[] a, int n, int key) {
        int pl = 0;
        int pr = n - 1;

        do {
            int pc = (pl + pr) / 2;
            if (a[pc] == key) {
                return pc;
            } else if (a[pc] < key) {
                pl = pc + 1;
            } else {
                pr = pc - 1;
            }
        } while (pl <= pr);

        return -1;
    }
}

 

- 복잡도

알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complexity) 라고 한다.

 

1. 시간 복잡도(time complexity) : 실행에 필요한 시간을 평가한 것

2. 공간 복잡도(space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

 

한 번만 실행하는 경우 복잡도는 O(1)로 표기.

n에 비례하는 횟수만큼 실행하는 경우 O(n)으로 표기.

O는 Order에서 따온 것으로. O(n)은 'O - n' , 'Order n', 'n의 Order'라고 읽는다.

 

일반적으로 O(f(n))과 O(g(n))의 복잡도를 계산하는 방법은 다음과 같다.

O(f(n)) + O(g(n)) = O(max(f(n), g(n))) 

 * max(a, b) 는 a와 b 가운데 큰 쪽을 나타내는 메서드

 

전체 복잡도는 차원이 가장 높은 복잡도를 선택한다.

 

이진 검색 알고리즘의 복잡도를 구현하면 O(log n)이다.

 

 

---