목록quickselect (1)

MODE::CREATIVE

[알고리즘] 선택 알고리즘 - 선형 시간 선택 알고리즘(QuickSelect)

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.참고교재: 쉽게 배우는 알고리즘(문병로)선택 알고리즘 1.선형 시간 선택 알고리즘(QuickSelect)2.최악의 경우 선형 시간 선택 알고리즘 선택 알고리즘이란  선택 알고리즘은 주어진 리스트에서 k번째로 작은(또는 큰) 요소를 찾는 알고리즘을 의미합니다. 이 알고리즘은 다양한 방법으로 구현될 수 있습니다. 선형 시간 선택 알고리즘은 최악의 경우에도 O(n)의 시간 복잡도를 가지는 알고리즘입니다. 이 알고리즘의 대표적인 예는 QuickSelect입니다. QuickSelect는 QuickSort 알고리즘을 기반으로 하며, 분할-정복 방식을 사용합니다. 피벗을 선정하고 이를 기준으로 리스트를 두 부분으로 나눈 후, k가 어느 부분에 있는지에 ..
Algorithms 2024. 2. 26. 16:18
이전 Prev 1 Next 다음