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

LeemHyungJun·2023년 6월 18일
0

Algorithm

목록 보기
9/10

1. Intro

  • 이진 트리의 노드가 n개 있다고 할 때 깊이 d는 dlg nd\ge lg\ n
  • 최악의 경우
    • 최소한의 비교 횟수 lg n+1\lfloor lg\ n \rfloor+1
      • 이진 검색이 최선의 알고리즘
  • 평균의 경우
    • lg n1\lfloor lg\ n \rfloor-1
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+xS[low]S[high]S[low](highlow)mid = low+\lfloor \frac{x-S[low]}{S[high]-S[low]}*(high-low) \rfloor
    • 평균의 경우 시간 복잡도 : lg(lg n)lg(lg\ n)
    • 최악의 경우는 순차검색과 같은 복잡도...

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

  • mid 값이 양 쪽 끝값이 되지 않도록 막아주기
  • gap의 초기값 = (highlow+1)1/2\lfloor (high-low+1)^{1/2}\rfloor
  • mid = MIN(high-gap, MAX(mid, low+gap))
  • 시간 복잡도
    • 평균의 경우 Θ(lg(lg n))\Theta(lg(lg\ n))
    • 최악의 경우 Θ((lg n)2)\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)=kmod(m)h(k)=k*mod(m)

7. 선택문제

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

8. 문자열 매칭

  • 원시적인 매칭
    • 한 칸씩 오른쪽으로 이동하면서 매칭 시도
    • i = i+1
  • 오토마타
    • 상태 전이함수 이용
  • Rabin-Karp
    • 문자열 패턴을 수치로 바꾸어 수치 비교를 통해 패턴 찾기
    • 각 자리수의 값을 저장해두고 -> v=p[m]+10p[m1]+102p[m2]+...+10m1p[1]v = p[m]+10*p[m-1]+10^2*p[m-2] + ...+10^{m-1}*p[1]
      • ex) p = [8,5,6,1]
    • ai1a_{i-1}을 이용해서 a_i 계산하는 개선법
      • ai=10(ai110m1A[i1])+A[i+m1]a_i=10*(a_{i-1}-10^{m-1}*A[i-1])+A[i+m-1]
    • mod함수를 이용한 개선법 -> 우연히 같은 경우가 발생할 수 있다는 문제점 존재함
      • bi=(d(bi1(dm1mod q)A[i1])+A[i+m1])mod qb_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 할 값을 설정하기

0개의 댓글