Tìm lượng tử thứ k của tập hợp các phần tử n. (Từ cormen)

Question

Số lượng k thứ k của tập hợp phần tử n là số liệu thống kê thứ tự k - 1 phân chia tập hợp đã sắp xếp thành các bộ có kích thước bằng nhau (đến trong 1). Đưa ra thuật toán O (n lg k) -time để liệt kê các số lượng k của tập hợp.

Giải pháp thẳng về phía trước là chọn mọi k, 2k, 3k .. ik phần tử nhỏ nhất, có thời gian chạy là O (kn) (k gọi để chọn thủ tục O (n)). Nhưng điều này có thể được tối ưu hóa để làm tốt hơn O (kn). Sau khi tìm thấy trung vị của trung vị tại chỉ mục 'i' trong quy trình chọn, chúng tôi thực hiện cuộc gọi đệ quy sau đây.

nếu chỉ số trung bình của trung vị i là> k, đệ quy gọi chọn thứ k phần tử nhỏ nhất trong mảng con bên trái A [0 ... i]

nếu i là < k, đệ quy chọn n - i + k phần tử nhỏ nhất trong phần con bên phải A [i + 1 ... n].

Các cuộc gọi đệ quy trên có thể được sửa đổi như dưới đây sẽ làm giảm hệ số 'k' thành 'log k' không?

nếu chỉ số trung vị của trung vị i> k, chọn đệ quy phần tử nhỏ nhất thứ k trong phần con bên trái A [0 ... i] và chọn đệ quy phần tử nhỏ nhất n - k trong phần con bên phải A [i + 1 ... n].

nếu i là < k, đệ quy chọn phần tử nhỏ nhất n - i + k trong phần con bên phải A [i + 1 ... n] và cũng đệ quy chọn phần tử nhỏ thứ k trong phần con bên trái A [ 0 ... i].

Cuộc gọi chính sẽ chỉ là chọn (A, k, n).

Answer 1

Tôi chưa trải qua cách tiếp cận của bạn, nhưng đây là câu hỏi từ Int. thuật toán bằng Cormen. Nhưng dù sao tôi cũng đang tự mình tìm kiếm giải pháp và tôi rất thích chia sẻ phiên bản thuật toán của mình. Hãy cố gắng bác bỏ tính chính xác của nó:

Tôi giả định rằng chúng tôi có một thuật toán tìm kiếm thống kê O (n). Vì vậy, tôi có thể tìm số liệu thống kê thứ k trong thời gian O (n). Giả sử tôi nói rằng tôi sẽ tìm tất cả các số lượng n/k kth bằng cách sử dụng phân chia và chinh phục sao cho:

Nếu tôi có phần tử n ', tôi chia mảng thành n'/2 phần, báo cáo ranh giới k-th quantiles cho cả hai phân vùng n '/ 2. Và báo cáo các số lượng còn lại đệ quy. Về bản chất những gì tôi đang làm là, sau khi phân vùng bằng cách sử dụng trung bình, tôi sẽ trích xuất quantile bên phải từ mảng bên trái, quantile trái nhất từ ​​phân vùng bên phải và sau khi cắt các mảng này chạy thuật toán đệ quy. Phân tích phức tạp của tôi xuất hiện là:

T (n, k) = 2 * T (n/2, k/2) + O (n).

Điều này hóa ra là O (nlogk) vì phần k/2 sẽ hội tụ nhanh hơn, mặc dù bạn có thể muốn giải quyết điều đó một cách nghiêm ngặt hơn. Ngoài ra, chúng tôi đã sử dụng n> k (rõ ràng từ vấn đề. Lưu ý rằng nhiệm vụ trích xuất 2 lượng và cắt mảng sẽ được thực hiện trong O (n)

Answer 2

Lưu ý rằng chúng tôi sử dụng một sửa đổi PARTITION. để trục được sử dụng như tham số đầu vào cuối cùng của nó.

Bạn bắt đầu với KTH-QUANTILES(A, 1, n, 1, k-1, k)

KTH-QUANTILES(A, p, r, i, j, k) 
n=A.length 
m=floor((i+j)/2) 
q=floor(m(n/k)) 
q=q-p+1 
q=SELECT(A, p, r, q) 
q=PARTITION(A, p, r, q) 
if i<m 
    L=KTH-QUANTILES(A, p, q-1, i, m-1, k) 
if m<j 
    R=KTH-QUANTILES(A, q+1, r, m+1, j, k) 
return L U A[q] U R 

Độ sâu của cây đệ quy là lg k, vì phân vùng được thực hiện xung quanh trung bình của các số liệu thống kê theo thứ tự nhất định (từ i đến j).

Trên mỗi cấp độ của cây đệ quy có Θ (n) hoạt động, do đó, thời gian chạy là Θ (nlgk).