중위수 중위수

중위수
클래스	선택 알고리즘
데이터 구조	배열
최악의 경우 공연
베스트 케이스 공연
최악의 경우 공간 복잡성	) n 보조

컴퓨터 과학에서 중위수는 대략적인 (중간) 선택 알고리즘으로, 주로 초기에 정렬되지 않은 배열에서 k번째 가장 작은 요소를 선택하는 퀵 선택 알고리즘을 위해 좋은 피벗을 공급하는데 자주 사용된다.중위수의 중위수는 선형 시간에서만 대략적인 중위수를 찾으며, 이는 제한적이지만 빠른 선택을 위한 추가 오버헤드입니다.이 근사치 중위수를 개선된 피벗으로 사용할 경우, 퀵 셀렉트의 최악의 경우 복잡성은 2차에서 선형까지 크게 감소하며, 이는 또한 어떤 선택 알고리즘의 점증상 최적 최악의 경우 복잡성이기도 하다.즉 중위수의 중위수는 좋은 피벗 요소를 만들어 점증적으로 최적이며 정확한 일반 선택 알고리즘(특히 최악의 경우 복잡성의 의미)을 구축하는 데 도움을 주는 대략적인 중위수 선택 알고리즘이다.

중위수 중위수는 또한 퀵소트에서 피벗 전략으로 사용되어 최적의 알고리즘을 제공할 수 있으며 최악의 경우 $O(n\log n)$ O $O(n\log n)$ $O(n\log n)$ $O(n\log n)$ n $O(n\log n)$ ) ${\displaystyle$ O $(n\log$ n $)}.$ 이 접근방식은 무증상 최악의 경우 복잡성을 상당히 잘 최적화하지만, 대신 평균을 위해 무작위 피벗을 선택함으로써 일반적으로 보다 우수하다.e $O(n)$ ( $O(n)$ ) $O(n)$ 선택 복잡성 $O(n)$ 및 평균 $O(n\log n)$ $O(n\log n)$ $O(n\log n)$ ) $O(n\log n)$ 정렬 복잡성 $O(n\log n)$ , 피벗 계산 오버헤드 없이.

마찬가지로 중위수 중위수는 k번째 최소값이 발견될 때까지 각 반복에서 피벗 선택을 위한 예비로서 하이브리드 인트로섹션 알고리즘에서 사용된다.이것은 다시 평균 사례 선형 성능에 더하여 최악의 경우 선형 성능을 보장한다. 즉, 장내 선택은 퀵 선택(임의 피벗, 기본값)으로 시작하여 양호한 평균 성능을 얻고, 진행 속도가 너무 느릴 경우 중위수에서 얻은 피벗으로 수정된 퀵 선택으로 되돌아간다.점증적으로 유사하지만, 그러한 하이브리드 알고리즘은 어떤 한정된 길이의 일정한 요인(평균-사례와 최악의 경우 모두)에 이르는 간단한 인트로셀렉트보다 더 낮은 복잡성을 가질 것이다.

알고리즘은 Blum et al. (1973년)에 발표되었으며, 따라서 저자의 성을 따서 BFPRT라고 부르기도 한다.원래의 논문에서 알고리즘은 "FIND"로 퀵 선택을 참조하면서 PICK로 언급되었다.

동기

Quick select는 평균적으로 선형 시간이지만, 피벗 선택이 잘 안 되는 2차 시간이 필요할 수 있다.빠른 선택이 분할 및 정복 알고리즘으로, 각 단계가 나머지 검색 집합의 크기로 O $O(n)$ ( $O(n)$ ) ${\displaystyle$ O $(n)}$ 시간을 $O(n)$ 갖기 때문이다.검색 세트의 크기가 (고정 비율에 따라) 기하급수적으로 빠르게 감소하는 경우, 이는 단일 단계의 $O(n)$ ( $O(n)$ ) {\ $displaystyle$ O(n $)}$ 인자에 $O(n)$ 곱한 기하학적 시리즈를 산출하여 전체 시간을 선형화한다.그러나 검색 세트의 크기가 선형으로(정확한 수의 요소에 의해, 최악의 경우 매번 한 요소씩만 감소) 느리게 감소하는 경우, 선형 스텝의 선형 합은 2차적인 전체 시간을 산출한다(형식적으로는 삼각형 수가 2차적으로 증가함).예를 들어, 이미 정렬된 데이터에 최대 요소를 퀵 선택으로 적용하고 매번 첫 번째 요소를 피벗으로 삼는 등 각 단계에서 가장 작은 요소를 선회할 때 최악의 경우가 발생한다.

만약 그 대신 "좋은" 피벗을 계속 선택한다면, 이것은 피할 수 있고 최악의 경우에도 항상 선형 성능을 얻을 수 있다."좋은" 피벗은 각 단계에서 검색 집합이 최소한 일정한 비율만큼 감소하므로, 따라서 기하급수적으로 빠르게 전체 시간이 선형으로 유지되고, 원소의 일정한 비율이 그 아래 및 위에 모두 있음을 확인할 수 있는 피벗이다.중위수는 좋은 피벗이며, 정렬에 가장 적합하고, 선택 항목에 가장 적합한 선택이며, 각 단계에서 검색 세트를 절반으로 줄인다.따라서 만약 어떤 사람이 선형 시간으로 중위수를 계산할 수 있다면, 이것은 각 단계에 선형 시간만 더하기 때문에 알고리즘의 전체적인 복잡성은 선형 상태를 유지한다.

중위수 알고리즘은 대략적인 중위수, 즉 30번째 백분위수와 70번째 백분위수 사이(중간 4십분위)가 보장되는 점을 계산한다.따라서 검색 세트는 최소 30% 감소한다.문제는 원래 크기의 70%로 줄어들어 고정비율이 작아진다.한두 가지 요소만 남을 때까지 현재 작은 세트에 동일한 알고리즘을 반복적으로 적용하면 n ${\frac {n}{1-0.7}}\approx 3.33{n}$ - ${\frac {n}{1-0.7}}\approx 3.33{n}$ ${\frac {n}{1-0.7}}\approx 3.33{n}$ 3 ${\frac {n}{1-0.7}}\approx 3.33{n}$ ${\$ 약 $3.33{n}}$ 의 비용이 발생한다.

알고리즘.

앞에서 설명한 바와 같이 퀵 선택 알고리즘에서는 중간값의 중위가 피벗 선택 전략으로 사용되는데, 가성 코드는 다음과 같다.조심해서 다루어라.left,right그리고n시행 시다음의 가성 부호는 다음과 같이 가정한다.left,right, 그리고 리스트는 하나의 기반 번호 매기기 그리고 저것들을 사용한다.select처음에는 다음과 같은 주장으로 1과 함께 호출된다.left그리고 리스트의 길이는 다음과 같은 논거로 한다.right. n번째 가장 작은 숫자의 실제 값이 아니라 목록을 재배열한 후 n번째 가장 작은 숫자의 인덱스를 반환한다는 점에 유의하십시오.

기능 select(목록, 왼쪽, n오른쪽)루프 돌아선 바로 그 때:nxpivotIndex 다음 다른 n 돌아오partition(목록 오른쪽, 왼쪽 pivotIndex, n)= 떠나pivotIndex:)pivot(목록, 좌회전)pivotIndex 돌려 n<>만약, 왼쪽 pivotIndex 후 바로:)pivotIndex-1 떠나:=pivotInde.x+1

서브루틴피벗은 실제 중위수 중위수 알고리즘이다.입력(길이 $n$ 의 목록)을 최대 5개 요소의 그룹으로 나누고, 서브루틴을 사용하여 각 그룹의 중위수를 계산한 다음, 이전 단계에서 발견된 ${\frac {n}{5}}$ 5 ${\$ 중위수의 ${\frac {n}{5}}$ 참 중위수를 재귀적으로 계산한다.^[1]피벗 호출이 선택된다는 점에 유의하십시오. 이 호출은 상호 재귀의 예입니다.

5이하 요소용 기능 pivot(목록, 좌회전)을 끓여오른쪽 −<> 남아 단지 중앙, 5그러면 partition5(목록, 좌회전)// 그렇지 않으면 나의 첫번째 n/5 위치에 왼쪽에서 5//로i'th 강의 부분 군 su의 중앙 자리에 있는 거 왼쪽에서 오른쪽으로 강의 서브 그룹의 medians 움직인다.bRiGht:subRight 을=나는 4+, 바로 그때 subRight: 돌아선 오른쪽 median5:스왑 list[median5]과 list[ 떠나+바닥((나는 − 남아)/5)]// partition5(목록, 나는,subRight)=:)(오른쪽 −을 떠났다)/10++1반환 select(목록, 왼쪽(( 옳−을 떠났다+바닥을 떠났다)/5)를 떠나n/5medians-of-five의 중선 compute.mid)

파티션 도우미 기능

선형 시간 내에 목록을 그룹화할 수 있는 파티션이라는 서브루틴이 있다(인덱스에서 범위).left로right)는 특정 요소 이하의 부분, 그와 동등한 부분, 요소 이상의 부분(삼원 분할)으로 세 부분으로 나뉜다.세 부분으로 그룹화하면 중위수가 일치 요소가 많거나 모두인 경우 선형 실행 시간을 유지할 수 있다.다음은 요소에 대한 파티션을 수행하는 유사 코드list[pivotIndex]:

함수 파티션(list, 왼쪽, 오른쪽, pivotIndex, n) pivotValue := list[pivotIndex] 스왑 목록[pivotIndex] 및 list[right] // 피벗을 끝 저장소로 이동색인 :=왼쪽 // 피벗보다 작은 모든 요소를 i용 피벗의 왼쪽으로 왼쪽에서 오른쪽으로 이동 - 목록[i] < pivotValue]인 경우 1 do 후 목록 스왑[store]색인] 및 목록[i] 증분 저장소인덱스 // 작은 요소 저장소 바로 뒤에 피벗과 동일한 모든 요소 이동IndexEq = 스토어스토어의 i에 대한 색인인덱스를 오른쪽으로 - 목록[i] = pivotValue인 경우 1 do 후 목록 스왑[store]IndexEq] 및 목록[i] 증분 저장소IndexEq 스왑 목록[오른쪽] 및 목록[저장소]IndexEq] // 피벗을 최종 위치로 이동 // n < store인 경우 원하는 위치를 고려하여 피벗의 복귀 위치인덱싱 후 스토어 반환n ≤ store인 경우 색인 // n이 더 작은 요소 그룹에 있음IndexEq return n // n이 피벗 리턴 저장소와 동일한 그룹에 있음IndexEq // n이 더 큰 요소 그룹에 있음

파티션5 서브루틴은 최대 5개의 요소로 이루어진 그룹의 중위수를 선택한다. 이를 구현하기 위한 쉬운 방법은 아래와 같이 삽입 정렬이다.^[1]의사결정 트리로도 구현할 수 있다.

함수 파티션5(list, 왼쪽, 오른쪽) i :=왼쪽 + 1인 반면, 오른쪽 j :=i는 왼쪽, 목록[j-1]은 스왑 목록[j-1]을 실행하고 목록[j] j := j - 1 i : = 1 return floor(왼쪽 + 오른쪽) / 2)는 왼쪽 + 1이다.

피벗 특성

${\frac {n}{5}}$ ${\frac {n}{5}}$ ${\$ ${\frac {1}{2}}\times {\frac {n}{5}}={\frac {n}{10}}$ ${n}{5}}$ 그룹 ${\frac {n}{5}}$ 중 절반의 그룹( ${\frac {1}{2}}\times {\frac {n}{5}}={\frac {n}{10}}$ 2 ${\frac {1}{2}}\times {\frac {n}{5}}={\frac {n}{10}}$ ${\frac {1}{2}}\times {\frac {n}{5}}={\frac {n}{10}}$ 5 = n ${\frac {1}{2}}\times {\frac {n}{5}}={\frac {n}{10}}$ ${\frac 스타일$ {1 $}{1$ }{1}:{2 $}}회$ {\ $frac{5}}={\frac}{10$ 이 피벗(메디안)보다 중위수가 적다.또한 그룹 수의 또 다른 절반(again, ${\frac {1}{2}}\times {\frac {n}{5}}={\frac {n}{10}}$ $×$ ${\frac {1}{2}}\times {\frac {n}{5}}={\frac {n}{10}}$ 5 = ${\frac {1}{2}}\times {\frac {n}{5}}={\frac {n}{10}}$ ${\frac {1}{2}}\times {\frac {n}{5}}={\frac {n}{10}}$ {\ $displaystyle$ {\ $frac{$ 1}{1}{1}:{ $1}}}\time$ {\ $frac {n}{$ 5}}}={\ $frac {n}{$ 10 ${\frac {1}{2}}\times {\frac {n}{5}}={\frac {n}{10}}$ 은 피벗보다 중위수를 더 크게 한다.피벗보다 중위수가 작은 ${\frac {n}{10}}$ ${\frac {n}{10}}$ ${\$ 그룹의 ${\frac {n}{10}}$ 각 그룹에는 피벗보다 작은 각각의 중위수보다 작은 두 개의 요소가 있다.따라서 n ${\frac {n}{10}}$ ${\$ 그룹 ${\frac {n}{10}}$ 각각에는 피벗보다 작은 최소 3개의 요소가 있다.마찬가지로 피벗보다 중위수가 큰 ${\frac {n}{10}}$ ${\frac {n}{10}}$ ${\$ 그룹의 ${\frac {n}{10}}$ 각 그룹에는 피벗보다 큰 각각의 중위수보다 큰 두 개의 요소가 있다.따라서 n ${\frac {n}{10}}$ ${\$ 그룹 ${\frac {n}{10}}$ 각각에는 피벗보다 큰 최소 3개의 요소가 있다.따라서 피벗은 $3\times {\frac {n}{10}}$ $3\times {\frac {n}{10}}$ n $3\times {\frac {n}{10}}$ ${\$ { $n}{10}}$ 보다 $3\times {\frac {n}{10}}$ 작으며 다른 $3\times {\frac {n}{10}}$ $3\times {\frac {n}{10}}$ $3\times {\frac {n}{10}}$ ${\$ 보다 $3\times {\frac {n}{10}}$ 크다.따라서 선택한 중위수는 알고리즘의 최악의 경우 선형 동작을 보장하는 30%/70%와 70%/30% 사이에서 정렬된 원소를 분할한다.시각화하려면:

0부터 99까지의 100개 원소의 랜덤화된 집합에 대해 1회 반복
	12	15	11	2	9	5	0	7	3	21	44	40	1	18	20	32	19	35	37	39
	13	16	14	8	10	26	6	33	4	27	49	46	52	25	51	34	43	56	72	79
미디안	17	23	24	28	29	30	31	36	42	47	50	55	58	60	63	65	66	67	81	83
	22	45	38	53	61	41	62	82	54	48	59	57	71	78	64	80	70	76	85	87
	96	95	94	86	89	69	68	97	73	92	74	88	99	84	75	90	77	93	98	91

(빨간색 = "(가능한 두 가지 중 한 가지) 중위수", 회색 = "숫자 <빨간색", 흰색 = "숫자 > 빨강색")

여기에 5-튜플을 중위수별로 정렬하여 표시하여 명확히 한다.피벗 요소로 사용하기 위해 중앙값만 있으면 되기 때문에 튜플을 정렬할 필요는 없다.

적색 위/좌측 모든 원소(100개 원소의 30%)가 적으며 적색 아래/우측 모든 원소(100개 원소의 다른 30%)가 더 크다는 점에 유의하십시오.

O(n) 작동 시간 증명

중위수 계산 재귀 호출은 중위수 ${\frac {n}{5}}$ 재귀 호출의 ${\frac {n}{5}}$ 가 n 5 ${\frac {n}{5}}$ {\ $displaystyle {\frac{n}{5$ 인 반면 다른 재귀 호출은 목록의 최대 70%에서 반복되기 때문에 최악의 경우 선형 동작을 초과하지 않는다. $T(n)$ ( $n$ ) {\ $displaystyle$ $T(n)}$ 을(를) 크기 n {\displaystyle $n}$ 의 배열에서 중위수 중위수 Quickselect 알고리즘을 실행하는 데 걸리는 시간으로 설정하십시오 $T(n)$ $n$ 그렇다면 우리는 이 시간이 다음과 같다는 것을 안다.

T(n)\leq T(n/5)+T(n\cdot 7/10)+c\cdot n.

어디에

$T\left({\frac {n}{5}}\right)$ $T\left({\frac {n}{5}}\right)$ ) ${\$ 부분은 $T\left({\frac {n}{5}}\right)$ (독립된) Quick selection을 ${\frac {n}{5}}$ 하여 n ${\frac {n}{5}}$ ${\$ 중위수를 ${\frac {n}{5}}$ 찾는 것은 k-smost 요소를 선택하는 특별한 경우일 뿐이므로)의 진정한 중위수를 찾기 위한 것이다.
$O(n)$ ( $O(n)$ ) $O(n)$ 용어 $O(n)$ $c\cdot n$ $c\cdot n$ ${\displaystyle c\cdot$ n $}$ 은 양쪽을 생성하기 위한 분할 작업에 대한 것으로 $c\cdot n$ , 그 중 하나는 우리의 Quickselection이 반복된다(각 원소를 n/5 그룹으로 구성하고 각 중위수를 O ( $O(1)$ ) ${\displaystysty$ O(1)로 $O(1)$ 만들기 $O(1)$ 위해 일정 횟수를 방문했다.
$T\left({\frac {7n}{10}}\right)$ $T\left({\frac {7n}{10}}\right)$ ) ${\$ 부분은 실제 Quickselect 재귀(최악의 경우, k-th ${\frac {7n}{10}}$ 가 ${\frac {7n}{10}}$ ${\frac {7n}{10}}$ ${\$ 의 ${\frac {7n}{10}}$ 크기가 될 수 있는 큰 파티션에 있는 경우)를 위한 것이다 $T\left({\frac {7n}{10}}\right)$ .

이것으로부터, 유도를 사용하는 것은 쉽게 그것을 보여줄 수 있다.

T(n)\leq 10\cdot c\cdot n\in O(n).

분석

핵심 단계는 총 길이가 원래 리스트보다 짧은 두 리스트와 감소 단계의 선형 요인을 선택하는 것으로 문제를 줄이는 것이다.이를 통해 전체 주행 시간이 선형임을 보여주는 간단한 유도를 할 수 있다.

다섯 가지 요소로 이루어진 집단의 구체적인 선택은 다음과 같이 설명된다.첫째로, 홀수 리스트의 중앙값을 계산하는 것이 빠르고 간단하다. 짝수 리스트를 사용할 수 있는 반면, 이것은 두 개의 중간 원소의 평균을 필요로 하는데, 이것은 단순히 하나의 정확한 중간 원소를 선택하는 것보다 느리다.둘째로 5는 중위수의 중위수가 작용하는 가장 작은 홀수다.With groups of only three elements, the resulting list of medians to search in is length ${\frac {n}{3}}$ , and reduces the list to recurse into length ${\frac {2}{3}}n$ , since it is greater than 1/2 × 2/3 = 1/3 of the elements and less than 1/2 × 2/3 = 1/3 of the elements.따라서 이는 여전히 검색해야 할 $n$ $n$ 요소를 $n$ 남겨두고 문제를 충분히 줄이지 않는다.그러나 개별 목록은 더 짧고, 그 결과 발생하는 복잡성을 Akra-Bazi 방법에 의해 $O(n\log n)$ $O(n\log n)$ $O(n\log n)$ $){\displaystyle O(n\log$ n $)}$ 로 구속할 수 있지만, 선형성을 증명하지는 않는다.

반대로 $g$ $g$ $g$ = 7개, 9개 또는 그 이상의 요소로 그룹화할 수 있으며, 이는 효과가 있다.이렇게 하면 중위수 목록의 크기가 ${\frac {n}{g}}$ g ${\$ 로 감소하고, 겹치는 선의 크기가 비례적으로 감소함에 따라 위 표의 사분면이 25%에 가깝기 때문에 3n/4(75%)에서 무증상으로 반복될 수 있다.이렇게 하면 스케일링 계수가 증상 없이 10에서 4로 감소하지만, 그에 따라 분할 작업에 $대한$ c $c$ 항이 증가한다 $c$ .더 큰 그룹의 중위수를 찾는 데는 시간이 더 걸리지만 상수 요인( $g$ $g$ 에만 따라 다름) $g$ 이므로 n이 증가해도 전체 성능이 바뀌지 않는다.실제로 최악의 경우 비교 횟수를 고려하면 상수인자는 ${\frac {2g(g-1)}{g-3}}$ - 1 ${\frac {2g(g-1)}{g-3}}$ ) ${\frac {2g(g-1)}{g-3}}$ - ${\frac {2g(g-1)}{g-3}}$ ${\$ 이다 ${\frac {2g(g-1)}{g-3}}$

그 대신 $다른$ 방식으로 n ${\displaystylen}$ 요소 $n$ 목록을 5개의 목록으로 나누고 각 요소의 중위수를 계산한 다음, 즉 상수가 아닌 상수 분수로 그룹화한다고 가정하면 각각 5개의 중위수를 계산해야 하기 때문에 문제를 명확하게 줄이지 않는다. ${\frac {n}{5}}$ ${\frac {n}{5}}$ ${\$ 요소 ${\frac {n}{5}}$ , 그리고 나서 최대 7 ${\frac {7}{10n}}$ ${\$ 의 길이 목록에 반복됨 ${\frac {7}{10n}}$ 3으로 그룹화할 때와 마찬가지로 개별 목록은 더 짧지만 전체 길이는 더 짧지 않으며, 따라서 초선형 한계만 입증할 수 있다. ${\sqrt {n}}$ ${\sqrt {n}}$ ${\displaystyle$ ${\$ $sqrt{n}$ 의 ${\sqrt {n}}$ 정사각형으로 그룹화하는 것도 마찬가지로 복잡하다 ${\sqrt {n}}$ .

참조

^ ^a ^b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.

Blum, M.; Floyd, R. W.; Pratt, V. R.; Rivest, R. L.; Tarjan, R. E. (August 1973). "Time bounds for selection" (PDF). Journal of Computer and System Sciences. 7 (4): 448–461. doi:10.1016/S0022-0000(73)80033-9.

외부 링크

"1996년 1월 30일의 선택 노트: 결정론적 선택", ICS 161: 알고리즘의 설계 및 분석, David Eppstein

[clrs-1] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.

[1]

Search