quick select1 6. Array(배열) - Quick Select 1. Quick Select란? - 정렬되지 않은 배열에서 N번째로 크거나 작은 수를 찾을 때 사용되는 알고리즘 - N번째 수를 찾기 위해서는 다음과 같은 방법을 사용할 수 있다. 1) 전체 요소를 오름차순으로 정렬한 후, N번째 수를 찾는 방법 - O(N log N)의 시간복잡도 2) Heap 정렬 - O(n log k)의 시간복잡도 - 1)의 방법보다 빠르다. 3) Quick Select - O(n)의 시간복잡도 - 가장 빠른 방법이다. - 이 중에서 가장 빠른 Quick Select에 대해서 알아보자. 2. Quick Select 개념 - Quick Select는 Partitioning(파티셔닝)을 이용한 알고리즘이다. ▶ Partitioning 이란? - Pivot 이라는 하나의 숫자를 기준으로 .. 2021. 9. 2. 이전 1 다음
