약 알고리즘 선택

Question

나는 selection algorithm에 대해 읽었으며 어쩌면 바보 같이 보입니다. 그러나 왜 우리는 배열을 5 가지 요소의 그룹으로 생각합니까 ?? 우리는 7 또는 3 요소로 그것을 고려할 수 있습니까 ?? 덕분에 또한이 목적을 더 잘 이해할 수 있도록 도와 줄 링크가 있습니까?

또한 3 개의 요소가있는 배열을 고려해도 여전히 n의 순서인데 이것이 왜 올바른지?

T(n)<=T(n/3)+T(n/3)+theta(n) 
claim: T(n)<=cn 
proof: For all k<=n : T(n)<=ck 
    T(n)<=(nc/3)+(nc/3)+theta(n) 
    T(n)<= (2nc/3)+theta(n) 
    T(n)<=cn-(cn/3-theta(n)) and for c>=3 theta(n) this algorithm with this condition will have an order of n,too !!!! 

Answer 1

나는 T (n)에 대해 실수했다고 생각합니다. T (n) = T (n/3) + T (2n/3) + O (n)이어야합니다.

T (n/3)는 피벗 (중앙값의 중앙값)을 찾습니다. 모든 n/3 그룹의 절반만이 피벗보다 중앙값이 작습니다. 이러한 그룹에는 피벗보다 작은 2 개의 요소가 있습니다. 2 * (1/2 * n/3) == n/3 요소를 피벗보다 작게 지정하십시오. 따라서 33 %만이 피벗보다 작아야하며 33 %는 피벗보다 커야합니다. 따라서, 더 나쁜 경우에는 다음 반복 (T (2n/3))에 대해 66 %를 유지합니다.

교정본을 읽을 수 없지만 증명할 수 없습니다. 권리?

Answer 2

약간의 인터넷 검색 결과로 this이 발견되었습니다. 왜 5에 관한 아주 작은 섹션이 있지만, 사용 가능한 가장 작은 가능한 홀수라고 말하는 것 이외에는 질문에 구체적으로 대답하지 않습니다 (중간 값을주는 것은 이상해야합니다). 3이 될 수 없다는 수학적 증거가 있습니다 (그러나 나는 그것을 스스로 이해하지 못합니다). 기본적으로 그것이 홀수 인 5 또는 그 이상일 수 있다고 말하는 것 같지만, 작은 쪽이 중간 값을 찾는 것이 더 빠를 것이기 때문에 작은 쪽이 더 좋을 것이라고 생각합니다.