Thuật toán trung vị của trung vị: tại sao chia mảng thành các khối có kích thước 5

Question

Trong thuật toán trung bình, chúng ta cần chia mảng thành các khối có kích thước 5. Tôi tự hỏi làm cách nào các nhà phát minh ra các thuật toán số ma thuật '5' và không, có thể là, 7, hoặc 9 hay cái gì khác?

Answer 1

Tôi nghĩ rằng nếu bạn sẽ kiểm tra "Proof of O (n) thời gian chạy" của trang wiki cho medians-of-medians algorithm:

Cuộc gọi đệ quy trung bình-tính không vượt quá trường hợp xấu nhất hành vi tuyến tính vì danh sách các trung vị là 20% kích thước của danh sách, trong khi cuộc gọi đệ quy khác recurses trên tối đa là 70% của danh sách, làm cho thời gian chạy

O (n) hạn cn là cho công việc phân vùng (chúng tôi đã truy cập từng phần tử một số lần stant, để tạo thành n/5 nhóm và lấy mỗi trung vị trong thời gian O (1)). Từ đó, sử dụng cảm ứng, người ta có thể dễ dàng thấy rằng

Điều đó sẽ giúp bạn hiểu, tại sao.

Answer 2

Số phải lớn hơn 3 (và một số lẻ, rõ ràng) cho thuật toán. 5 là số lẻ nhỏ nhất lớn hơn 3. Vì vậy, 5 đã được chọn.

Answer 3

Bạn cũng có thể sử dụng các khối có kích thước 3 hoặc 4, như được hiển thị trong giấy Select with groups of 3 or 4 bởi K. Chen và A. Dumitrescu (2015). Ý tưởng là sử dụng thuật toán "median of medians" hai lần và chỉ phân vùng sau đó. Điều này làm giảm chất lượng của trục nhưng nhanh hơn.

Vì vậy, thay vì:

T(n) <= T(n/3) + T(2n/3) + O(n) 
T(n) = O(nlogn) 

một nhận:

T(n) <= T(n/9) + T(7n/9) + O(n) 
T(n) = Theta(n)