Medians and Order Statistics
Phần này có 1 vài vấn đề cần quan tâm như: - Median - i-th order statistic - Selection problem ------- 1, i-th order statistic i-th order statistic là phần tử có thứ tự i trong dãy đã xếp hay còn gọi là phần tử nhỏ thứ i trong dãy. Median( theo môn MAS có thể dịch là trung vị) là phần tử halfway. Nếu n lẻ, median nằm ở giữa. Nếu n chẵn, sẽ có median upper và median lower: Phát biểu bài toán: Input: Cho một dãy n phần tử phân biệt và số i (1<=i <= n) Output: Đưa ra phần tử lớn hơn chính xác i-1 phần tử khác trong dãy. (Nói cách khác đưa ra phần tử nhỏ thứ i trong dãy). Xét bài toàn tìm minimum và maximum trong một dãy chưa được sort, ta mất (n-1) phép so sánh cho từng loại. Vậy ta phải mất 2n-2 phép so sánh để tìm cả max và min. Liệu có cách nào hiệu quả hơn? Ta có thể chỉ mất 3*|n/2| phép so sánh bằng cách: - Chia thành các cặp phần tử - So sánh từng cặp với nhau - Với mỗi cặp lại so sánh với min, max hiện tại => Chỉ mất 3 phép so sán...