- 선형 중간값 찾기 알고리즘을 설명하고, 시간 복잡도가 O(n)인 것을 보여라.
선형 중간값 찾기 알고리즘은 주어진 n개의 원소가 저장된 배열에서 중간값을 찾는 알고리즘이다. 이 알고리즘은 QuickSort와 같이 분할 정복 알고리즘을 사용하는 것과 달리 단순한 선형 탐색 방법을 사용한다.
선형 중간값 찾기 알고리즘의 절차는 다음과 같다.
배열의 첫 번째 원소를 선택하고, 배열을 왼쪽 부분집합, 오른쪽 부분집합, 중간 부분집합으로 분할한다.
1.중간 부분집합의 크기를 계산한다.
2.중간 부분집합의 크기가 n/2인 경우 중간값을 찾았으므로 해당 원소를 반환한다.
3.중간 부분집합의 크기가 n/2보다 작은 경우, 왼쪽 부분집합에 중간값이 존재하므로 왼쪽 부분집합에 대해 재귀적으로 중간값을 찾는다.
4.중간 부분집합의 크기가 n/2보다 큰 경우, 오른쪽 부분집합에 중간값이 존재하므로 오른쪽 부분집합에 대해 재귀적으로 중간값을 찾는다.
5.시간 복잡도는 n/2번의 탐색을 수행하므로 O(n)이다. 따라서 선형 중간값 찾기 알고리즘의 시간 복잡도는 Θ(n)이다.
- 해싱 함수에서 계수 a 가 0이 되면 안되는 이유는 무엇인가?
해싱함수의 수식은 h(ak + b))mod p 인데, 여기서 키값은 k 이며 그 계수 a 가 0이된 다면 키가 해싱 함수의 값을 결정하지 못하게 된다. 따라서 k의 존재를 살리기 위해 계수 a는 0이 되어선 안된다.
- 8.4 를 읽고 8.1 예시를 풀어라.
만약 키가 균일하게 분포되어 있고, n = 2m이라면, 성공한 검색의 평균 비교 횟수는?
해시 키가 균등하게 분포되어 있으면, 각 바구니에는 평균 n/m개의 키가 들어간다. 이 때, 바구니에 들어있는 키의 개수가 5개 이하라면, 선형 검색 알고리즘을 사용하여 바구니 내에서 키를 검색한다.
바구니에 들어있는 키의 개수가 5개 이상이라면, Median of Medians 알고리즘을 사용하여 바구니 내에서 중간값(median)을 찾는다. 그리고 중간값을 피벗(pivot)으로 사용하여 바구니를 두 그룹으로 분할한다.
그 다음, 키를 찾고자 하는 바구니를 선택하고, 선택된 바구니 내에서 선택된 그룹에서만 검색을 수행한다. 이 과정을 재귀적으로 수행하여 키를 찾는다.
검색에 필요한 평균 비교 횟수는 O(1) (5/2) + O(1) (n/m - 5/2) + O(1) log2 log2 (n/m) 이다. 여기서 O(1) (5/2)는 바구니 내에서 선형 검색을 수행하는 경우의 평균 비교 횟수이다. O(1) (n/m - 5/2)는 Median of Medians 알고리즘을 사용하여 바구니를 분할하고, 선택된 그룹에서만 검색을 수행하는 경우의 평균 비교 횟수이다. O(1) log2 log2 (n/m)는 재귀적으로 바구니 내에서 검색을 수행할 때마다 중간값을 찾는데 필요한 비교 횟수이다.
따라서, 평균 비교 횟수는 1.39가 된다.
4.birthday dataset을 이용하여 정렬되지 않은 데이터 셋에 넣고, basic quick sort, intelligent quick sort, paranoid quick sort, tuple sort 의 네가지 알고리즘을 이용하여 정렬하고 비교하여라.
- birthday data 정렬되지 않은 데이터 셋에 넣기
import pandas as pd
df = pd.read_csv('/Users/hansunkyoung/Projects/algorithm/BirthdayData.csv', encoding='UTF-8')
birth_df = df.iloc[1:, 2:3]
birth_df.fillna(0)
_birth_lst = birth_df.values.tolist()- Basic quick sort:
가장 기본적인 퀵 소트 알고리즘 중 하나, Pivot으로는 리스트의 첫 번째 요소인 A[0]를 선택. 선택된 pivot을 중심으로 배열을 partition하여 pivot보다 작은 원소들과 큰 원소들로 나누고, 이후 재귀적으로 각 partition에서 퀵소트 알고리즘을 반복
def basic_quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[-1]
smaller, larger = [], []
for i in range(len(arr) - 1):
if arr[i] <= pivot:
smaller.append(arr[i])
else:
larger.append(arr[i])
return basic_quick_sort(smaller) + [pivot] + basic_quick_sort(larger)
birth_arr = birth_df['생년월일'].tolist()
basic_sorted = basic_quick_sort(birth_arr)
- Intelligent quick sort:
Pivot으로 리스트의 중앙값을 선택하는 퀵 소트 알고리즘
def intelligent_quick_sort(arr):
if len(arr) <= 1:
return arr
else:
med = statistics.median([arr[0], arr[-1], arr[len(arr)//2]])
pivot_idx = arr.index(med)
pivot = arr.pop(pivot_idx)
smaller, larger = [], []
for i in range(len(arr)):
if arr[i] <= pivot:
smaller.append(arr[i])
else:
larger.append(arr[i])
return intelligent_quick_sort(smaller) + [pivot] + intelligent_quick_sort(larger)
birth_arr = birth_df['생년월일'].tolist()
intelligent_sorted = intelligent_quick_sort(birth_arr)
- Paranoid quick sort:
Pivot으로 가장 좋은 선택이 되는 요소를 선택하는 퀵 소트 알고리즘, 피봇 요소로 기존 리스트 중에서 임의로 추출한 값 중 가장 좋은 선택이 되는 값을 사용.
def good_choice(arr):
"""
Returns the value in arr with the most unique digits.
"""
max_count = -1
max_value = -1
for val in arr:
count = len(set(str(val)))
if count > max_count:
max_count = count
max_value = val
return max_value
def paranoid_quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = good_choice(arr)
smaller, larger = [], []
for i in range(len(arr)):
if arr[i] <= pivot:
smaller.append(arr[i])
else:
larger.append(arr[i])
return paranoid_quick_sort(smaller) + [pivot] + paranoid_quick_sort(larger)
birth_arr = birth_df['생년월일'].tolist()
paranoid_sorted = paranoid_quick_sort(birth_arr)
- Tuple sort:
날짜 데이터를 월과 일로 구분하여 정렬하는 알고리즘
def good_choice(arr):
"""
Returns the value in arr with the most unique digits.
"""
max_count = -1
max_value = -1
for val in arr:
count = len(set(str(val)))
if count > max_count:
max_count = count
max_value = val
return max_value
def paranoid_quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = good_choice(arr)
smaller, larger = [], []
for i in range(len(arr)):
if arr[i] <= pivot:
smaller.append(arr[i])
else:
larger.append(arr[i])
return paranoid_quick_sort(smaller) + [pivot] + paranoid_quick_sort(larger)
birth_arr = birth_df['생년월일'].tolist()
paranoid_sorted = paranoid_quick_sort(birth_arr)
이들의 시간 복잡도를 비교하면, Basic quick sort는 최악의 경우 O(n^2)의 시간복잡도를 가지고 있으며, Intelligent quick sort와 Paranoid quick sort는 최악의 경우 O(nlogn)의 시간복잡도를 가지고 있다. Tuple sort의 경우, 선택한 구현 방식에 따라 시간복잡도가 다르지만 일반적으로 O(nlogn)의 시간복잡도를 가지고 있다.
