[WIL] Day 11 (기말준비 Day 2)

<알고리즘>

 

Upper bound이해: 최악의 경우에도 이 정도 이상은 안올라간다(어떤 그래프가 있을때), 그럼 오메가는 최고의 경우에도 이 정도 이하는 안올라간다?

 

재귀함수, 마스터 정리

어떤 알고리즘의 시간 복잡도 함수 T(n)이 다음과 같은 형태일때.

T(n) = a * T(n/b) + c * n^k

이 함수 T(n)의 시간복잡도 클래스는 다음과 같다.

T(n) ∈ θ(n^k) if a < b^k

T(n) ∈ θ(n^k log2n), if a = b^k

T(n) ∈ θ(n^logba), if a > b^k

 

마스터 정리 문제 2개: https://www.youtube.com/watch?v=-bm0-k7UeV8&list=PLHqxB9kMLLaO2Zxb5exYYcN-Tin5pE-sK&index=2

 

Divide and conquer:

1. divide
2. Conquer
3. Combine

Merge sort가 이를 사용하는 알고리즘, 그리고 binary search도 divide and conquer를 사용한다. 

Merge sort의 recurrence는 T(n) = 2*T(n/2) + θ(n)으로 표현할 수 가 있다. 뜻은 맨처음에 배열을 절반으로 나누어서 T(n/2)가 되고 2개의 나누어진 배열임으로 2를 곱하고, 남은 배열들을 다시 합치거나 divide할때 θ(n)이 됨(그냥 combine 과정 생각하면 됨).

 

Binary Search는 T(n)=1*T(n/2)+θ(1)으로 recurrence표시가능. 일단은 중간값을 찾고 절반으로 나눈지만 이때 하나의 배열은 버리기 때문에 1*T(n/2)이고 아마 중간값찾는것 때문에 θ(1)인것 같은데…divide combine할게 없어서 θ(1)이라는데… 

 

어떤값의 지수(a^n)도 recurrence로 표시하면  T(n) = T(n/2) + θ(1). 이거 계산할때는 단순하게는 브루트포스 방식대로 a*a*a*a*a*a….이런식으로 계산을 할수도 있겠지만 divide and conquer을 사용하면 time complexity를 줄일수가 있다. 

 

행렬의 곱셈도 divide and conquer으로 나눌수 있다. 행렬이 2x2라고 할때 첫번째 행렬의 값은 (n/2)*(n/2)+(n/2)(n/2)임, 그리고 이게 4개니까 n/2끼리의 곱셈이 8번 발생하게 되는거임, 한번 T(n)에 수행할때마다. 그리고 T(n/2)에 대해서 또 (n/4)(n/4)의 곱셈이 8번씩 발생…. 

그래서 T(n) = 8T(n/2) + θ(n^2)가 되겠다. 

 

Quick Sort:

Base on divide and conquer. 또 “in place” sorting이라는데 다른 새로운 배열이 필요없고 주어진 input이 담긴 배열로 쇼부를 볼수 있다라는 뜻임. 

아래는 퀵소트의 divide conquer단계로 설명:

divide: pivot하나를 선정 (일반적으로 중간값), 그리고 해당 값 왼쪽, 오른쪽으로 배열 나눔.

conquer: 두개의 배열을 recursively sort. 

combine: nothing

수도코드:

QUICKSORT(A, p, r):

  If p < r

    Then q <- PARTITION(A, p, r)

       QUICKSORT(A, p, q-1)

       QUICKSORT(A, q+1, r)

 

Initial call: QUICKSORT(A, 1, n), 그리고 q는 pivot의 위치 

 

PARITITON의 수도 코드

PARTITION(A, p, r)

  X <- A[P]    첫번째 값

  I <- p

  For j <- p + 1 to r

     Do if A[j] <= x

           Then  I <- I + 1

                  Exchange A[I] <-> A[j]

  Exchange A[p] <-> A[I]

  Return I

 

partition은 초장에 i는 피봇의 인덱스, 그리고 j는 피봇 오른쪽의 인덱스를 가리킴. j에 있는 값과 partition값을 비교. 만약에 pivot값보다 크면 그냥 j+1해서 오른쪽으로 보내고 만약에  pivot값보다 작다면 해당값과 i+1의값과 자리를 바꾼다. 그리고 i=i+1. 그렇게 j가 r까지 가도록 반복하고 그 반복이 끝나면 마지막으로 pivot값과 i에 있는 값과 자리를 바꾼다. 

코딩을 할때 loop의 invariant를 항상 생각하라. 해당 invariant의 조건을 만족할때까지만 루프를 돌도록하자. 

 

Analysis of quick sort 

quicksort의 worst case는? -> 배열이 모두 정렬되었거나, 거꾸로 sort되었을때이다. 왜? pivot이 항상 맨 앞이여서. 그러면 왼쪽에 있는 값이 n번 반복할때마다 0개임. 그럼 오른쪽에 있는 n-1값을 계속 n-1번씩 반복해서 찾게됨. 

Worst case의 recurrence tree는 다음과 같다. T(n) = T(0) + T(n-1) + cn. 뜻은, T(0)은 왼쪽이나 오른쪽에 sort해야할 배열의 갯수가 0개고, 한쪽에만 n-1개가 있는것. cn은 partition process의 횟수이다. 

그럼 nice인 상황은??? nice한 상황은 배열을 동등하게 나눌때. 그럼 T(n) = 2*T(n/2) + cn. 거의 merge sort랑 같음. 

 

Randomized quick sort

별견 없고, 이번에는 pivot을 맨 처음 값이 아닌 랜덤한 값으로 고르는 경우. 이런 경우엔 최악의 상황을 피할 수 있다. 

 

Paranoid quick sort

랜덤으로 피봇정하고 partition을 수행. 수행하는데 그 split하는 비율이 1:9를 안넘으면 pivot정하는것 부터 다시 수행. 대신 extra cost가 든다.

 

퀵소트는 대부분의 경우 merge sort보다 좋은 성능을 발휘하는데 왜 그런지 알아보자

Randomized quick sort Analysis

k값이 0~n-1가 가능한 값이라고 할때 Xk에서 1인 상황은 지정한 k값이 k:n-k-1인 경우가 나오는 경우 Xk=1, 다른 경우인 경우에는 Xk=0. 그럼으로 Xk가 1일 확률은 1/n이다. 

갑자기 기대값, 내가 원하는 값이 나오는 확률 * 1, 이외에는 그냥 0값곱하면 됨. 

그래서 이걸 어떻게 쓰냐, k는 0~n-1값이니까 이걸로 모든 상황, 그러니까 partition이 왼쪽으로 0개 오른쪽으로 n-1개, 왼쪽1개 오른쪽 n-2개, 왼쪽 2개 오른쪽 n-3개….. 이 상황들의 모든 값의 기대값을 구하는 속셈. 

결국 시그마 k=0부터 n-1, Xk(T(k) + T(n-k-1)+θ(n))으로 계산가능. 근데 어차피 Xk가 1인 경우는 하나 그래서 결국에는 (T(k) + T(n-k-1)+θ(n)) 이 부분만 살아남는다. 그래서 이 식을 이용해서 T의 기댓값이 nlogn보다 작거나 같다를 판별할것. 그래서 해당 시그마 식을 기댓값 때려버리면 어떻게 약분이 가능해지고. 여기다가 math induction인가를 넣어버린다. 해당 시그마식이 anlogn보다 작거나 같다라고 가정하고, 주어진 시그마anlogn으로 치환해서 induction해버리면 뭐 구할 수 있다. (식이 복잡해서 찾아보면서 기억)

 

해쉬 테이블

해쉬 테이블은 density dependent search으로 특징될수가 있다. ratio느낌 number of elements / memory space. 

Direct access table, 내가 알고 있는 그 해쉬테이블. 그 원하는 키값을 넣어주면 값이 바로 나오는. 빠른데 단점은 메모리를 확보해야되는것. 최대값이 2^64면 엄청 큼…

그래서 better method 그게 hash table.다른점은 그전보다 훨신 적은 메모리의 hash table를 갖는다라는것이다. 충돌이 일어나면 linked list으로 chain 이어주면 된다. 충돌하는 이유는 키의 값이 table의 범위보다 크기 때문이다(좀만 생각하면 아!)

좋은 해쉬 function을 만들기 위해서는 모든 해쉬 function의 키는 다 같은 확률로 input을 받을 수 있도록 설계해야한다, 그리고 각각은 독립적이어야한다. 이러한 특징을 가진 애들이 simple uniform hashing이라고 한다. 

테이블에서 키의 갯수가 m개라고 하고, 테이블에 넣을 수 있는 slot갯수가 n개라고 할때 테일블의 load factor는 n/m이다(average number of keys per slot). 그래서 해시테이블의 자세한 time complexity는 θ(1+a)이다. 그리고 알파가 상수인 상황. 알파가 작으면 작을수록 좋다. 

 

Division method

Define h(k) = k mod m 

Pick m to be a prime. 8이나 16같은 divisor가 2인 애들은 피해라. 

 

Multiplication method

이 상황에서는 m=2^r, w-bit words

Hash function는 이렇게 정의됨. h(k) = (A*k mod 2^w) right shift (w-r), 이때 A는 홀수 정수이고 2^(w-1) < A < 2^w이다. 

 

Resolve collision by open addressing.

얘는 원래 테이블 말고 다른 데이터 구조가 필요가 없음. 그래서 n < m을 유지한다. 

얘는 key값과 probe 두 값이 필요로 한다. 그리고 output은 테이블상의 위치를 리턴한다. 

 

Linear Probing 

h(k,i) = (h’(k)+i) mod m, 간단하지만 primary clustering이란걸 겪게 된다, 이게 뭐냐면 average search time을 길게한다. 많은 부분이 연속적으로 점유된게 primary clustering. 그렇게되면 primary clustering에 들어갈 확률도 높고, i가 점점 커진다. 그리고 primary clustering이 점점 커진다. i가 1씩 증가하는것도 문제. 가능한한 clustering짧게 하는게 좋다. 

 

그래서 나온게… 

Double hashing.

h(k,i) = (h1(k) + ih2(k)) mod m, 결과가 좋다. H2(k)가 prime to m이어야한다. linear에서는 i가 1씩 늘어났지만 여기서는 한번에 여러값을 점프함. h2만큼씩 점프하는 듯. 

 

Open addressing의 성능 분석

///(여기서부터 해시 테이블 내용 다시 봐야됨, 다행히 이전 내용보다는 어렵지 않은듯?)

 

Insertion을 할때는 몇번의 probing이 필요한가? 이전에 unsuccessful search할때 1/(1-a)만큼 필요힘. insertion도 마찬가지이다. 왜냐? 빈자리를 찾아야 하는데 이는 unsuccessful search와 같다.