중간 값을 찾는 범위의 하한값

n 개의 숫자 목록이 주어 졌으므로 중앙값보다 크거나 같은 숫자를 찾고자합니다. 이 문제의 최악의 복잡성에 대한 하한을 배우고 싶습니다. 중간 값을 찾는 하한선은 3 (n-1)/2라는 것을 압니다. 그러나 우리가 인 숫자를 이상의 중간 값으로 찾으려면 동일 할 것입니다.중간 값을 찾는 범위의 하한값

출처

2013-06-05 Jason

[Dor et al. (2001) "중앙값 선택에 대한 하한선"] (http://www.nada.kth.se/~johanh/mediansdma.pdf), 하한은 적어도 2 * n * + o (* n *) 비교는 3 (* n * -1)/2 이상입니다. 문제에 대해 다른 가정을하고 있습니까? – Simon

목록의 첫 번째 요소 중 가장 큰 요소 (+1)가이 기능을 가질 것이라고 생각합니다. n/2 + 1 요소를 확인하고 가장 큰 요소를 저장하면 최대/2 - 1 요소가 중간 값 후보보다 클 수 있습니다. 따라서 선택한 숫자는 숫자의 위쪽 절반에 해당합니다. 즉, 숫자의 중앙값보다 크거나 같습니다.

그럼 n/2+1에서 찾을 수 있습니다.

당신이 필요합니다

최악의 경우 : N/2 비교 식 및 N/2 + 1 과제.

최상의 사례 : n/2 개의 comparsions 및 1 개의 할당. 댓글에

Edit: 답변 :

예. n이 짝수이면 모든 임의의 요소가 중간 값 이상이고 확률은 적어도 0.5입니다. 왜 "적어도 0.5"? 거의 모든 숫자가 중간 값과 동일한 테스트 사례가있을 수 있습니다. 이 경우 확률은 더 높아집니다. 올바른 확률을 알고 싶으면 모든 요소를 확인해야합니다. 다른 숫자를 가진 다른 테스트 케이스에서 임의의 요소는 확률값 0.5로 정렬 된 목록의 위쪽 절반에있게됩니다.

n이 홀수이면 확률이 0.5보다 큰 임의의 숫자에이 기능이 적용됩니다. 그것은 n/2-0.5 요소가 중간 값보다 작고 n/2+0.5 요소가> = 중간 값 (일반적인 테스트 경우)입니다. 최소 확률을 0.5로하고 싶다면 수정을해야합니다. 증거가없는 아이디어가 있습니다. 작동하지 않는다면 누군가가 나를 조롱 할 것입니다. 목록에서 2 개의 임의 값을 선택하십시오. 더 작은 것은 적어도 0.5 확률의 유효한 솔루션이 될 것입니다.

출처

2013-06-05 23:35:19 gkovacs90

상수는 big-O 복잡도에 영향을 미치지 않기 때문에 기술적으로 'O (n/2 + 1) = O (n) = O (2n) = O (9999999n)'입니다. 따라서 'O'를 제거 할 수 있습니다. – Dukeling

@Dukeling 당신 말이 맞아요, 제가 그것을 제거했습니다. – gkovacs90

확률이 0.5 인 유효한 결과를 반환하는 무작위 알고리즘을 작성할 수 있습니까? – Jason

중간 값을 찾는 범위의 하한값

답변

관련 문제