Thời gian chạy sắp xếp với hộp con tìm kiếm hộp đen tìm kiếm

Question

Giả sử bạn có một chương trình con hộp đen có thể trích xuất tối đa từ một mảng các phần tử n trong thời gian (log n)^a, trong đó 0 <= a <= 1. Bạn đang cố gắng tạo một thuật toán phân loại tối ưu giúp sử dụng chương trình con này.

Giải pháp rõ ràng là gọi chương trình con trên toàn bộ mảng, hoán đổi giá trị tối đa với phần tử cuối cùng, sau đó gọi lại thường trình con theo số A[1, n-1] qua A[1, 2].

Có một thuật toán tốt hơn chạy nhanh hơn thời gian n*(log n)^a hay giải pháp hiển nhiên tối ưu?

Answer 1

Tôi không biết câu trả lời chính xác, nhưng đây là một số kết quả mà gợi ý câu trả lời có thể là ngây thơ một:

Giả sử chúng tôi chia đầu vào thành 4 miếng (4 có thể được thay thế bằng k);

Phân loại trên mỗi phần trong số 4 phần mất n/4 * (log (n/4)^a), kết hợp các kết quả cần (n/2 + n/2 + n) = 2n;

n/4 * (log (n/4)^a) * 4 = n (logn^a) -n/4 * (log4)^a,

tổng thời gian = n (logn^a) - n/4 * (log4)^a + 2n

Tuy nhiên, nếu a = 1, rhs = n (log (n)^a); nếu một < 1, rhs> n (log (n)^a). Vì vậy, ngay cả khi xem xét từ góc độ thế giới thực hơn là quan điểm Big-Oh, cách tiếp cận phân chia & chỉ có thể làm chậm nó xuống nếu < 1 và không có lợi ích khi a = 1.

Tôi không biết nếu có các thủ thuật khác, tuy nhiên. Hy vọng điều này có thể ít nhất gây ra một số ý tưởng!

Answer 2

Không. Trong kỳ vọng, chúng ta cần bit Ω (n log n) từ hộp đen để sắp xếp n mục. Khi được gọi trên một mảng có kích thước k, hộp đen chạy cho (log k) ^a các bước và trả về bit k log, với tốc độ khoảng (log k) ^{1 - một bit} mỗi bước. Tỷ lệ này được chuyển hướng lên trên bởi (log n) ^{1 - a}, vì vậy thuật toán hiển nhiên là tối ưu tiệm cận.