[알고리즘/Week 4] Assignment 4

문제

1. Describe linear median finding algorithm. Show that its time complexity is Θ(n).

Linear median finding 알고리즘은 intelligent quick sort의 다른 이름으로, quick sort에서 사용되는 기준점(pivot) 값을 애초에 median, 즉 중앙값으로 설정하여 더 용이하게 숫자를 비교할 수 있도록 만든 알고리즘이다. 여기서 중앙값이란 데이터 개수를 딱 절반으로 나누는 수를 의미한다. 이 중앙값과 n개의 숫자를 비교하여 숫자가 중앙값보다 작으면 앞으로, 크면 뒤로 보내는 알고리즘을 loop를 통하여 반복한다. 

중앙값이 데이터의 가장 크거나 작은 값인 경우 데이터의 각 요소를 모든 요소와 비교해야하기 때문에 n^2번의 비교가 필요하며, 이때 시간 복잡도는 O(n^2)이다. 그러나 이는 매우 드문 경우이며, 평균/최선의 경우 알고리즘은 n-1번의 비교만 필요하며 n과 선형적(linear)으로 증가하므로 linear median finding 알고리즘의 시간 복잡도는 θ(n)이다. 

 

2. In hashing function, why the coefficient a should not be 0?

해시 함수는 입력 키를 해시 함수에 적용하기 전에 크기와 위치를 조정하는 데 사용되며, 해시 함수의 목적은 일반적으로 입력 키를 작은 값의 범위로 매핑하는 것이다. 이 때, 매핑된 값은 일반적으로 배열의 인덱스가 된다. 만약 a의 계수가 0이라면 a와 곱해지는 수는 항상 0이 되기 때문에 입력 키의 값과 상관 없이 항상 같은 결과가 출력될 것이다. 이렇게 되면 모든 키는 같은 배열의 인덱스로 매핑되어 키를 고르게 분배하지 않는 나쁜 해시 함수를 만들게 된다.