1. Describe linear median finding algorithm. Show that its time complexity is Θ(n).
linear median finding은 Intelligent Quick Sort에 속한다. 이는 Quick Sort의 기준점(피벗)을 끝이 아닌 중앙에 두는 방식이다.
예시를 들어 설명을 해보면, [1,8,2,9,4,5,7]의 배열이 있다고 가정해보자.
1. 이의 피벗을 배열의 중앙에 있는 9로 잡는다. [1,8,2,9(피벗),4,5,7]
2. 피벗(기준점)을 기준으로 피벗보다 작은 값은 왼쪽에 피벗보다 큰 값은 오른쪽으로 정렬한다.
현재 배열에서 피벗인 9보다 큰 값이 없으므로 모두 피벗보다 왼쪽에 정렬이 되었다. [1,8,2,4,5,7,9(피벗)]
3. 새롭게 정렬된 배열에서 중앙에 있는 값을 피벗을 잡는다. [1,8,2,4(피벗),5,7,9]
4. 피벗(4)를 기준으로 피벗보다 작은 값은 왼쪽에 피벗보다 큰 값은 오른쪽에 정렬한다. [1,2,4(피벗),8,5,7,9]
5. 4번의 배열은 [1,2][4(피벗)][8,5,7,9]로 볼 수 있다.
6. 5번의 배열을 오름차순으로 배열하면, [1,2]는 이미 오름차순으로 정렬이 되어있기 때문에 정렬할 필요가 없다. 피벗의 오른쪽에 있는 [8,5,7,9]를 오름차순으로 정렬되어 있지 않아 정렬을 해야 한다.
7. [8,5,7,9]에서 9를 피벗으로 잡고, 8,5를 비교하였을 때, 8>5이므로 8,5를 swap한다. [5,8,7,9]
8. [5,8,7,9]에서 5,7를 비교하였을 때, 5<7이므로 swap하지 않는다.
9. [5,8,7,9]에서 8,7를 비교하였을 때, 8>7이므로 swap한다. [5,7,8,9]
1번~9번까지의 과정을 통해 정렬되지 않은 배열을 quick sort방식을 통해 오름차순으로 정렬하였다. [1,2,4,5,7,8,9]
n을 배열의 원소 개수라고 가정하면, 각 단계에서 각각의 원소를 오름차순으로 정렬하기 위해 피벗을 올바른 위치에 두기 위한 비교 연산을 n번 시행해야 한다. 그러므로 Quick Sort를 사용하여 median finding을 하는 것의 시간 복잡도는 Θ(n)이다.
2. In hashing function, why the coefficient a should not be 0?
해시 함수는 많은 공간에 할당된 데이터를 원래의 공간(많은 공간)보다 작은 공간으로 데이터를 할당하는 역할을 한다. u 대신 m=O(n) slot에 더 작은 동적 직접 접근 배열을 저장한다.
h(k) : {0,...u-1} -> {0,...,m-1} (u>m)
Hash(p,m) = ((h(ak+b)) mod p ) mod m 이 해시 함수의 식이다.
Hash(p,m): Hashing family function
h: hashing function
k: key
b: noise
mod : 나머지 값 출력
p: 충분히 큰 prime number
m: 줄이고 싶은 space 크기
a,b ∈ {0,...p-1} , a ≠ 0
여기서 a가 0이 되면, 해시함수가 상수 함수가 되어 모든 데이터가 같은 장소로 할당이 되는 문제가 발생한다. 그러므로 a는 0이 되면 안된다.
3. Read chapter 8.4. Solve example 8.1 in the chapter.
예제 8.1
만약 키가 균일하게 분포되어 있고 n=2m이라면, 실패한 검색은 각각 2m/m = 2번의 비교만 필요하고, 성공한 검색은 평균 비교 횟수가 다음과 같다.
2m/2m+1/2 = 3/2
정리 8.4를 참고하면, n개의 키가 m개의 바구니에 균일하게 분포되어 있다면, 실패한 검색에서 비교 횟수는 n/m이다. 이는 키가 균일하게 분포되어 있기 때문에 각 바구니의 키 개수는 n/m이다. 즉 이는 실패한 검색은 모두 n/m 번의 비교를 필요로 한다는 걸 뜻한다.
이를 통해 예제 8.1에서 실패한 검색 비교 횟수를 계산하면, n/m = 2m/m = 2이다.
정리 8.5를 참고하면, n개의 키가 m개의 바구니에 균일하게 분포되어 있고, 각 키가 검색 키가 될 확률이 거의 같다고 하면, 성곻안 검색의 평균 비교 횟수는 n/2m+1/2이다. 이는 각 바구니의 평균검색시간은 n/m개의 키를 순차검색하는 경우 평균 검색시간과 같다는 걸 뜻한다.
이를 통해 예제 8.1에서 성공한 검색 평균 비교 횟수를 계산하면, n/2m+1/2=2m/2m+1/2 = 1+1/2 = 3/2이다.
만약 키가 균일하게 분포되어 있으면 검색시간은 매우 작다. 그러나 비록 해시가 그렇게 예외적으로 좋은 결과를 줄 가능서이 있음에도 불구하고, 혹자는 검색이 거의 순차검색에 가깝게 퇴보하지 않기 위해서는 그래도 이분검색을 사용해야 한다고 주장할지 모른다.
4. Use the birthday dataset, do the followings:
4.1. Put them into your unsorted array using set.
4.2. Order them with the birth day. You should consider the following algorithms.
- Basic quick sort
Pivot X = A[0] or A[n-1]
- Intelligent quick sort
Pivot X = median of A
- Paranoid quick sort
Pivot X = E(Good choice)
Paranoid quick sort는 처음에는 random 하지만 좋은 pivot이 나올 때까지 반복하는 정렬방식이다.
1. Repeat
-> find X(pivot) randomly in A(array) partition
2. Until
-> Good pivot을 찾을 때 까지
3. Recursion
-> Left array & Right array (X(pivot)을 기준으로 X보다 작으면 Left array, X보다 크면 Right array로 정렬한다.)
- Tuple sort
1) The month comes first, and the date second
2) The date comes first, and the month second
4.3. Compare the sorting algorithms
Basic quick sort ,Intelligent quick sort, Paranoid quick sort :
Basic quick sort는 pivot을 첫번째 데이터 또는 마지막 데이터로 잡는다. 최악의 경우 1개씩 모두 돌아야 하므로 T(n) = T(1) + T(n-1) +⊖(n)으로 O(n²) 만큼 Time complexity가 걸린다.
Intelligent quick sort는 pivot을 처음부터 중앙에 있는 데이터로 잡는다. pivot보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 정렬시킨다. 정렬시킨 배열에서 다시 중앙에 있는 데이터를 pivot으로 잡아 위와 같은 과정을 반복한다. pivot을 random하게 잡으므로 최악의 경우가 될 확률이 크다. 최악의 경우 O(n²)만큼 Time complexity가 걸린다.
Paranoid quick sort는 배열에서 pivot을 랜덤하게 잡고 좋은 pivot을 찾을 때까지 반복한다. 좋은 pivot은 배열의 왼쪽 1/4와 오른쪽 1/4 부분을 제외한 부분에서 나온 데이터이다. Paranoid quick sort는 2번 틀리면 좋은 pivot이 나오기 때문에 최악의 경우 Time complexity를 계산해보면, T(n) = T(1/4*n) + T(3/4*n) + (iteration(2번 틀리면 좋은 pivot 나옴[좋은 pivot의 구간이 1/2이기 때문])) + c(random한 값) + n(recursion한 값) 이다. 따라서 T(O(nlgn))만큼 걸린다.
Tuple sort: 영향력이 작은 date를 먼저 sort한 후에 영향력이 큰 month를 sort하는 것이 더 합리적이다.
