a

Câu hỏi Giải thích thuật toán Median of Medians


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

Trục được chọn vừa 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 nó một chút sáng suốt cho tôi. Tôi thấy khó hiểu logic.


12
2017-09-22 16:48


gốc




Các câu trả lời:


Hãy nghĩ về tập hợp các số sau:

5 2 6 3 1

Số trung bình của các số này là 3. Bây giờ nếu bạn có một số n, nếu n > 3, sau đó nó lớn hơn ít nhất một nửa số ở trên. Nếu n < 3, sau đó nó nhỏ hơn ít nhất một nửa số ở trên.

Đó 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ó n / 5 số. Điều này là hiển nhiên.

Bây giờ nếu bạn nhận được số trung bình của những con số đó (gọi nó là m), nó lớn hơn một nửa trong số đó và nhỏ hơn nửa còn lại (theo định nghĩa trung bình!). Nói cách khác, m nó to hơn n / 10 số (mà 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 n / 10 số (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 vị là k và bạn có m > k, sau đó m cũng lớn hơn 2 số khác (bản thân chúng 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 đó m lớn hơn môi trường của nó, m cũng lớn hơn hai số khác. Điều này làm cho nó ít nhất 3 số (2 số + chính giữa) trong mỗi số n / 10 5 nhóm phần tử nhỏ, nhỏ hơn m. Vì thế, m ít nhất là lớn hơn 3n/10 số.

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


14
2017-09-22 16:58



Chỉ cần một câu hỏi khác, làm thế nào để phương pháp này đảm bảo rằng con số này sẽ là trung bình? Trung bình là một số phân vùng mảng thành nửa trên và nửa dưới. Vậy con số 30-30-70 này có ý nghĩa gì? - SexyBeast
Vâng, trung bình là ở giữa, nhưng m (trong văn bản ở trên) không phải là trung vị của tất cả các số. Nó là trung bình chỉ có 1/5 số (là trung bình của 5 nhóm phần tử nhỏ hơn). Hãy thử đọc đoạn cuối cùng với sự chú ý nhiều hơn. Cuối cùng, nơi nó được kết luận rằng mlớn hơn ít nhất 3n/10 của các con số, cũng có nghĩa là m lớn hơn ít nhất 30% số. Vì vậy, cuối cùng, nó giống như m lớn hơn ít nhất 30% và nhỏ hơn ít nhất 30%. Có 40% còn lại mà chúng tôi không chắc chắn. - Shahbaz
Sau đó, làm thế nào đến nó cho một phân vùng 50-50 trung bình? Phân vùng 50-50 được đưa ra bởi trung bình bình thường, phải không? - SexyBeast
Nó không cho 50-50 phân vùng trung bình. Nó luôn mang đến một nơi nào đó giữa 30-70 và 70-30 (có thể bạn có thể gọi nó 50-50 trung bình?), nhưng đó không phải là vấn đề. Cho quicksort để cung cấp cho O(nlogn) thời gian phức tạp, nó cần để có thể chia mảng thành các phân vùng tỷ lệ thuận với kích thước của mảng. Đó là những gì mang lại cho logn độ sâu đệ quy. 30-70 phân chia đã cho 3n/10 và 7n/10 chia tỷ lệ thuận với n. Vì vậy, mặc dù nó không phải là hoàn hảo 50-50, nó vẫn sẽ mang lại độ sâu đệ quy lôgarít (ngoại trừ nó không phải là log trong cơ sở 2, nhưng cơ sở 10/7) - Shahbaz


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


3
2018-05-05 22:46