Giải thích thuật toán Median of Medians

Question

Cách tiếp cận Median of medians rất phổ biến trong quicksort thuật toán phân vùng loại để tạo ra trục xoay khá tốt, sao cho nó phân chia mảng đồng nhất. Logic của nó được đưa ra trong Wikipedia là:

Trục được chọn nhỏ hơn và lớn hơn một nửa các phần tử trong danh sách trung vị, khoảng n/10 phần tử (1/2 * (n/5))) cho mỗi nửa. Mỗi phần tử trong số này là trung bình là 5, làm cho nó nhỏ hơn 2 phần tử khác và lớn hơn 2 phần tử khác bên ngoài khối. Do đó, trục xoay nhỏ hơn 3 (n/10) phần tử bên ngoài khối, và lớn hơn một phần tử 3 (n/10) khác bên ngoài khối. Do đó, trung vị được chọn chia các phần tử ở đâu đó giữa 30%/70% và 70%/30%, đảm bảo hành vi tuyến tính xấu nhất của thuật toán.

Ai đó có thể giải thích một chút sáng suốt cho tôi. Tôi thấy khó hiểu logic.

Answer 1

Hãy suy nghĩ về các thiết lập sau các con số:

5 2 6 3 1 

Trung vị của những con số này là 3. Bây giờ nếu bạn có một số n, nếu n > 3, thì nó lớn hơn ít nhất một nửa số ở trên. Nếu n < 3, thì nó nhỏ hơn ít nhất một nửa số ở trên.

Vì vậy, đó là ý tưởng. Tức là, đối với mỗi bộ 5 số, bạn sẽ nhận được số trung bình của chúng. Bây giờ bạn có số n/5. Điều này là hiển nhiên.

Bây giờ, nếu bạn nhận được số trung vị của các số đó (gọi là m), số này lớn hơn một nửa số và nhỏ hơn nửa kia (theo định nghĩa trung bình!). Nói cách khác, m lớn hơn n/10 số (chính chúng là trung vị của 5 nhóm phần tử nhỏ) và lớn hơn một số khác là n/10 (một lần nữa là trung vị của 5 nhóm phần tử nhỏ).

Trong ví dụ trên, chúng tôi thấy rằng nếu trung bình là k và bạn có m > k, sau đó m cũng là lớn hơn 2 con số khác (nghĩa là bản thân nhỏ hơn k). Điều này có nghĩa là đối với mỗi nhóm trong số 5 nhóm phần tử nhỏ hơn, trong đó m lớn hơn mức trung bình, m lớn hơn hai số khác. Điều này làm cho nó có ít nhất 3 số (2 số + số trung vị) trong mỗi số n/10 nhóm phần tử nhỏ 5, nhỏ hơn m. Do đó, m ít nhất là lớn hơn số 3n/10.

Logic tương tự cho số phần tử m lớn hơn.

Answer 2

Giải thích về mức trung bình - của - trung vị thuật toán để tìm ra số nguyên lớn nhất thứ k ra khỏi n cũng có thể được tìm thấy ở đây: http://cs.indstate.edu/~spitla/presentation.pdf