1. Describe linear median finding algorithm. Show that its time complexity is Θ(n).
선형 중앙값 찾기 알고리즘은 n개의 원소로 구성된 배열에서 중앙값을 찾는 알고리즘입니다. 이 알고리즘은 다음과 같은 단계를 따릅니다.
1) 배열을 정렬한다.
2) 중앙값을 찾는다.
import heapq
lowar=[]
highar=[]
median=0
def MaxHeap(a):
heapq.heappush(lowar,-1*a)
def gMaxHeap():
a=heapq.heappop(lowar)
return -1*a이 알고리즘의 시간 복잡도는 배열을 정렬하는 데 O(n log n)의 시간이 소요되고, 중앙값을 찾는 데 O(1)의 시간이 걸리기 때문입니다. 따라서 전체적으로는 O(n log n) + O(1) = Θ(n)이 된다.
2. In hashing function, why the coefficient a should not be 0?
충돌을 최소화 하기 위함이다.
3. Read chapter 8.4. Solve example 8.1 in the chapter.
example 8.1) 만약 키가 균일하게 분포되어 있고 n = 2m 이라면, 실패한 검색은 각각 2m/m = 2 번의 비교만 필요하고, 성공한 검색은 편균 비교 횟수가 다음과 같다.
2m/2m + 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)
- 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