검색 알고리즘

• 검색 알고리즘이란
• 선형 검색(linear search)
• 이진 검색(binary search)
• 나이브한 문자열 검색 알고리즘
• KMP 문자열 검색 알고리즘

Linear Search(선형검색)

하나에 한개씩 찾는 게 맞는지 대조해보면서 끝까지 반복하는 것.

첫부분에서 시작해서 끝부분으로 이동하면서 한 번에 하나의 항목을 확인, 끝에서 첫부분으로도 가능.

이미 자바스크립트에 선형검색 메소드가 있음

• indexOf
• includes
• find
• findIndex

이 함수들의 소스코드(source code)를 살펴보면, 선형검색 알고리즘을 확인할 수 있음.

Linear Search의 Big-O는 O(n)이다.

찾아야 하는 리스트가 길면 길수록 소요되는 시간이 증가한다.

만약 리스트 배열의 길이가 100만개가 넘어간다면?

찾는 것이 첫번째에 있다면 바로 찾겠지만 맨 뒤에 있다면 검색을 100만번 해야한다.

그렇다면 평균을 내면 n보다 작지 않을까? → 그렇지 않다. 0.25n이나 0.1n이나 모두 O(n)이다.

선형검색은 데이터가 분류되지 않았을 때 사용할 수 있는 가장 좋은 방법이다.

Binary Search(이진검색)

이진 검색은 분류된 배열을 대상으로만 작동한다.(오름차순, 문자열 알파벳 순 등)

한번에 하나씩 비교하던 선형검색과 달리 한번에 리스트의 절반씩 처리한다.

검색해야 하는 리스트의 중간지점 요소를 꺼내 찾는 대상과 비교한다.

순서가 뒤라면 앞에 리스트 절반을 버린다. 순서가 앞이라면 뒤에 리스트 절반을 버린다.

남은 리스트의 중간점을 찾는다 → 반복.

기본적인 개념은 분할 정복(devide and conquering)

배열을 두 부분으로 나누고 중간점을 선택해 좌측 절반과 우측 절반 중 하나를 선택하고 나머지는 버림.

정렬되어 있지 않은 데이터에는 이진 검색을 수행할 수 없다.

function binarySearch(arr, elem) {
    var start = 0;
    var end = arr.length - 1;
    var middle = Math.floor((start + end) / 2);
    while(arr[middle] !== elem && start <= end) {
        if(elem < arr[middle]) end = middle - 1;
        else start = middle + 1;
        middle = Math.floor((start + end) / 2);
    }
    return arr[middle] === elem ? middle : -1;
}

binarySearch([2,5,6,9,13,15,28,30], 103)

이진검색으로 배열에서 특정 요소를 찾는 코드.

시간복잡도 Big-O 는 어떻게 될까?

최선의 경우 → O(1) 중간값이 바로 찾는 값일때.

최악의 경우 → O(log n) 찾는 값이 없을때.

찾는 값이 없다면, 배열의 길이가 16개라고 가정하면,

첫번째 단계에서 8개로, 두번째 단계에서 3개로, 세번째 단계에서 1개로 줄어든다.

4번째 단계에서 없다는 걸 확인하게 된다.

log n 은 2의 몇 거듭제곱으로 n을 얻을 수 있는지 나타내는 것.

log2 16 = 4 이다. 2의 네제곱이 16이니까.

즉 O(log n)에서는 n의 크기를 두 배로 늘릴 때마다 그냥 한 단계를 더 추가하기만 하면 된다.

Big-O 중에서 O(1) 다음으로 빠르다.

문자열 검색 알고리즘

Naive String Search

가장 기본적으로 대조하는 방식 O(n*m) 의 시간복잡도를 가진다.

n은 전체 텍스트, m은 찾는 문자열.

KMP 알고리즘

KMP(knuth-morris-pratt) 사람이름을 딴 알고리즘 이름.
특정 패턴 문자열에서 다른 문자열을 찾음.

일반적인 naive search보다 효율적이다.

패턴 문자열의 접두사와 접미사를 이용하여 일치하지 않는 문자열을 다시 검색하지 않고 문자열 검색을 빠르게 수행하는 방식.

아직 이해를 못했다... 내용 보충 예정.