Algorithm : 계산 복잡도 (검색 문제)

1. Intro

• 이진 트리의 노드가 n개 있다고 할 때 깊이 d는 $d\ge lg\ n$
• 최악의 경우
  • 최소한의 비교 횟수 $\lfloor lg\ n \rfloor+1$
    • 이진 검색이 최선의 알고리즘
• 평균의 경우
  • $\lfloor lg\ n \rfloor-1$

2. Binary Search

void binsearch(int n, const keytype S[], keytype x, index& location)
{
	low = 1; high = n;
    location = 0;
    while(low <= high && location == 0)
    {
    	mid = (low+high)/2;
        if(x==S[mid])
        	location = mid;
        else if(x < S[mid])
        	high = mid - 1;
       else
       		low = mid + 1;
    }
}

3. 보간 검색

• Linear Interpolation
  • $mid = low+\lfloor \frac{x-S[low]}{S[high]-S[low]}*(high-low) \rfloor$
  • 평균의 경우 시간 복잡도 : $lg(lg\ n)$
  • 최악의 경우는 순차검색과 같은 복잡도...

4. 보강된(robust) 보간 검색법

• mid 값이 양 쪽 끝값이 되지 않도록 막아주기
• gap의 초기값 = $\lfloor (high-low+1)^{1/2}\rfloor$
• mid = MIN(high-gap, MAX(mid, low+gap))
• 시간 복잡도
  • 평균의 경우 $\Theta(lg(lg\ n))$
  • 최악의 경우 $\Theta((lg\ n)^2)$

5. 트리 구조를 사용한 동적 검색

• 정적 검색은 배열을 통해.. / 데이터가 한번에 저장 후 추가나 삭제 진행 안함
• 동적 검색은 트리를 통해.. / 데이터가 수시로 삭제 및 추가

이진 검색 트리

검색 시간 향상을 위한 트리 구조

• AVL 트리
  • 균형을 항상 맞추기 -> 좌 우 서브트리의 높이 차이가 최대 1인 이진 탐색 트리
• B-트리
  • 가장 간단한 형태인 2-3 트리
• red-black 트리

6. 해싱(Hashing)

• 해싱을 할 때 충돌이 발생하는 문제 해결하는 방법
  • Open hashing
    • 해싱이 효율적이 되기 위해서 키(n)가 바구니(m)에 균일하게 분포되어야 함
    • 바구니에 평균적으로 n/m개의 키를 가지게 함
  • Closed hashing
    • linear probing : 왼->오 로 이동하면서 이미 쓰고 있으면 한 칸 오른쪽으로 밀어주기
      • 문제점 : 데이터가 삭제될 경우 원래 비어있던 것인지 아니면 있었는데 지워진 것인지 알 수 없다.
    • quadratic probing : 위와 같지만 한칸이 아니라 여러 칸 밀어주기
    • double hashing : h_1이 충돌이 되면, h_2 함수 사용하기
• 단순한 형태의 해쉬함수
  • $h(k)=k*mod(m)$

7. 선택문제

• 키가 n개인 리스트에서 k번째로 큰 키를 찾는 문제 (정렬되지 않은 경우)
  • 기존 방식
    • max 키 찾기 : n-1번의 비교를 통해 구할 수 있다.
    • min & max 키 찾기 : $W(n)=2(n-1)$
  • 키를 짝 지워서 최소키 최대키 찾기
    • n/2만큼 비교를 통해 짝지은 두개의 값들 중 작은 값과 큰 값을 분류
    • n/2-1번의 비교를 통해 나눠진 그룹(작은 그룹 & 큰 그룹)에서 가장 작은 값과 큰 값 찾기
    • 총 $O(\frac{3n}{2})$의 비교
• 차대키 찾기(second largest key)
  • 기존 방식
    • 최대키를 먼저 찾고 (n-1) 다음 최대키를 찾기 (n-2)
    • 총 2n-3 비교
  • Tournament Method
    • 토너먼트를 진행해서 우승자가 최대 키
    • 진 팀을 이긴 팀의 리스트 만들기
    • 리스트에서 최대값을 찾으면 이것이 차대키
    • 총 $n+lg\ n-2$
• k번째 작은 키 찾기
  • 기존 방식
    • 정렬 후 k 번째 선택하기 $\Theta(n lg\ n)$
  • partition 사용
    • selection(l,n,k)
      • $W(n)=n(n-1)/2$
      • $A(n)=3n$
  • O(n) 방식
    • select(k,S)
      • 5개의 묶음으로 만들기
      • 묶음 내에서 정렬
      • 묶은 것들 중 가운데 값을 모아 M 생성
      • M에서 $\lceil|M|/2 \rceil$ 로 가운데 찾기
      • 분류된 곳에서 골라서 해당 범위에 맞는 곳에서 추가적인 search (작아진 문제에 대해 select)

8. 문자열 매칭

• 원시적인 매칭
  • 한 칸씩 오른쪽으로 이동하면서 매칭 시도
  • i = i+1
• 오토마타
  • 상태 전이함수 이용
• Rabin-Karp
  • 문자열 패턴을 수치로 바꾸어 수치 비교를 통해 패턴 찾기
  • 각 자리수의 값을 저장해두고 -> $v = p[m]+10*p[m-1]+10^2*p[m-2] + ...+10^{m-1}*p[1]$
    • ex) p = [8,5,6,1]
  • $a_{i-1}$을 이용해서 a_i 계산하는 개선법
    • $a_i=10*(a_{i-1}-10^{m-1}*A[i-1])+A[i+m-1]$
  • mod함수를 이용한 개선법 -> 우연히 같은 경우가 발생할 수 있다는 문제점 존재함
    • $b_i = (d*(b_{i-1}-(d^{m-1}mod\ q)*A[i-1]) + A[i+m-1])mod\ q$
• Boyer-Moore
  • 비교할 단어의 맨 뒤부터 검색하여 같지 않은 경우 jump해서 검색할 수 있다.
  • i = i + jump[A[i+m-1]]
  • 같은 문자가 있는 경우 작은 값으로 jump 할 값을 설정하기