2023 spring Algorithm
week04 homework
Problem Set 4
1. Describe linear median finding algorithm. Show that its time complexity is Θ(n).
linear median finding algorithm은 중앙값(주어진 데이터에서 가운데 위치한 값)을 찾는 알고리즘을 말한다. 중앙값을 찾는 알고리즘 중 가장 간단한 방법은 데이터를 정렬한 후, 중간에 위치한 값을 선택하는 것이다.
linear median finding algorithm 의 시간 복잡도는 데이터를 정렬하는 과정에서 시간을 많이 할애하기 때문에 정렬이 되어있는 경우 시간복잡도가 O(n)이 될 수 있다.
2. In hashing function, why the coefficient a should not be 0?
해싱 함수에서 계수 a가 0이 되면, 모든 입력 값에 대해 동일한 해시 값이 반환되기 때문에 해시 충돌이 많이 발생한다. 해시 충돌은 두 개 이상의 입력값이 동일한 해시값으로 매핑되는 경우를 말한다.
예를 들어 해시함수 h(x) = a * x + b가 았을 때 계수 a가 0이라면 h(x)는 항상 같은 값(b)를 반환한다. 따라서 해시 충돌이 많이 발생하게 되며, 이는 해시 테이블의 성능을 저하시키고, 탐색속도를 늦추게 된다.
따라서 hashing fuction에서 계수는 0이 되지 않고 해시 충돌을 최소화해 해시 함수의 성능을 향상시킬수 있도록 해야한다.
3. Read chapter 8.4. Solve example 8.1 in the chapter.
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
tuple sort에선 뒤에 있는 값을 기준으로 먼저 정렬을 하고, 앞에 있는 값들을 정렬하는 것이 더 효율적이다.
