선택
-
최악의 경우 선형시간 선택 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 29. 13:38
최악의 경우 선형시간 선택 최악의 경우에도 선택 알고리즘의 수행 시간이 Θ(n)이 되는 것을 보장하는 선택 알고리즘이다. 최악의 경우 선형시간 선택 알고리즘 분할 알고리즘으로 배열을 n개 씩의 그룹으로 나누고 그룹의 중간 값들의 중간 값을 이용해 선택 알고리즘을 수행한다. 최악의 경우 선형시간 선택 알고리즘 LinearSelect(A[], p, r, i) { 1. 원소의 총 수가 5개 이하이면 원하는 원소를 찾고 알고리즘을 끝낸다. 2. 전체 원소를 5개씩의 원소를 가진 ┌n/5┐개의 그룹으로 나눈다. 3. 각 그룹에서 중앙값을 찾는다. + 이렇게 찾은 중앙값들을 m1, m2,..., m┌n/5┐이라 하자. 4. m1, m2,..., m┌n/5┐들의 중앙값 m을 재귀적으로 구한다. 5. M을 기준 원소로..
-
평균 선형시간 선택 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 28. 13:49
평균 선형시간 선택 퀵 정렬의 분할 알고리즘을 이용하여 n 번째 원소를 빠르게 찾아내는 선택 방식이다. 평균 선형시간 선택 알고리즘 분할 알고리즘으로 두 개의 영역으로 나눈 뒤 n 번째 원소가 왼쪽에 포함되면 왼쪽 배열을 아니면 오른쪽 배열을 선택하는 과정을 반복하여 n 번째 원소를 찾는다. 평균 선형시간 선택 알고리즘 Select(A[], p, r, i) { if (p = r) then { return A[p]; } q ← Partition(A, p, r); k ← q - p + 1; if (i < k) then { return Select(A, p, q - 1, i); } else if (i = k) then { return A[q]; } else { return Select(A, q + 1, r, ..
-
선택 알고리즘 개요프로그래밍 기초/알고리즘 2021. 7. 27. 12:38
선택 알고리즘 주어진 집합에서 특정한 순서의 원소를 찾는 것을 선택 알고리즘이라고 한다. 이때, 정렬되지 않은 집합에 대해 특정한 순서의 원소를 찾을 때 시간 복잡도가 최대한 Ο(n)에 가깝게 되도록 하는 것이 선택 알고리즘의 의의이다. 선택의 종류 평균 선형시간 선택 퀵 소트의 분할 알고리즘을 응용한 것으로 기준 값의 위치보다 작은 값을 갖는 순서를 찾는 경우 왼쪽 그룹을 선택하고 기준 값의 위치보다 큰 값을 갖는 순서를 선택하는 경우 오른쪽 그룹을 선택하는 것을 반복하여 원하는 순서의 원소를 찾는 방식, 평균 Ο(n) / 최악의 경우 Ο(n²) 최악의 경우 선형시간 선택 최악의 경우에도 선형시간의 수행 시간을 보장하기 위해 중간 값이 끝 값이 되지 않도록 하기 위해 준간 값을 전체 그룹에서 찾아내도록..