Algorithm - Note

Written on September 22nd , 2023 by Hyunwoo Soung

임시 정리용

1. 평균 선형 시간 선택 알고리즘

• 기본적으로 배열에서 i번 째 작은 원소를 찾을 때 사용
• 퀵정렬 시 기준 원소로 분할하면 기준 원소가 몇번 째 원소인지 확인 가능
• 해당 위치보다 i가 작으면 왼쪽, 크면 오른쪽에서만 재귀로 선택
• 평균적으로 \(\Theta(n)\) 시간이 소요되지만, 최악의 경우 \(\Theta(n^2)\)의 시간이 소요됨.

2. 최악의 경우에도 선형 시간을 보장하는 선택 알고리즘

• 분할을 일정 비율로 고정시켜 최악의 경우에도 \(\Theta(n)\)을 보장하는 형태이다.
• 배열을 5개씩 묶은 그룹으로 나눈다.
• 각 그룹에서 중앙값(중간값을 의미하는 듯 하다)을 기준으로 그룹들을 분할한다.
• 두 그룹 중 적합한 쪽을 선택해 재귀 반복한다.
• 분할까진 알겠는데 이해가 잘 안감… 구현해봐야 할 것으로 예상…