선택 알고리즘 개요

  선택 알고리즘 

주어진 집합에서 특정한 순서의 원소를 찾는 것을 선택 알고리즘이라고 한다.

 

이때, 정렬되지 않은 집합에 대해 특정한 순서의 원소를 찾을 때 시간 복잡도가 최대한 Ο(n)에 가깝게 되도록 하는 것이 선택 알고리즘의 의의이다.

 

선택의 종류

• 평균 선형시간 선택 퀵 소트의 분할 알고리즘을 응용한 것으로 기준 값의 위치보다 작은 값을 갖는 순서를 찾는 경우 왼쪽 그룹을 선택하고 기준 값의 위치보다 큰 값을 갖는 순서를 선택하는 경우 오른쪽 그룹을 선택하는 것을 반복하여 원하는 순서의 원소를 찾는 방식, 평균 Ο(n) / 최악의 경우 Ο(n²)
• 최악의 경우 선형시간 선택 최악의 경우에도 선형시간의 수행 시간을 보장하기 위해 중간 값이 끝 값이 되지 않도록 하기 위해 준간 값을 전체 그룹에서 찾아내도록 만든 방식, 최악의 경우 Ο(n)

 

Algorithm/Randoms.txt at main · NadanKim/Algorithm · GitHub

NadanKim/Algorithm

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘