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?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
Trả lời
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.
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.
Nó không phải là lớn hơn tan 3 (và lẻ), xem câu trả lời của tôi dưới đây. –
Có, nhưng đó là một thuật toán khác. Nó chỉ là một biến thể nhỏ của thuật toán OP được hỏi về - nhưng nó vẫn là một thuật toán khác. OP hỏi "tại sao trong thuật toán cụ thể này chúng ta cần phải sử dụng khối 5", và không "là có một biến thể trên thuật toán này, nơi chúng tôi có thể sử dụng các khối nhỏ hơn". Họ đã cố gắng để hiểu làm thế nào một cái gì đó đã được tính toán hơn là cố gắng tìm nếu có cái gì đó khác nhau mà có thể làm điều đó tốt hơn. – rabensky
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)
- 1. Hiểu "trung bình của trung vị" thuật toán
- 2. Hiểu thuật toán lựa chọn trung bình?
- 3. việc tìm kiếm các trung bình của 5 yếu tố
- 4. Thuật toán OpenMp C++ cho tối thiểu, tối đa, trung bình, trung bình
- 5. Tìm trung vị trong nhiều phạm vi phụ của danh sách không có thứ tự
- 6. thay đổi kích thước với trung bình hoặc rebin một mảng 2ngày NumPy
- 7. Tìm trung tâm của nhiều vị trí trong Google Maps
- 8. Cách đặt vị trí trung tâm phía dưới của tooltip
- 9. chuỗi thuật toán chuyển vị
- 10. Thuật toán để chia nhỏ mảng thành các mảng phụ đồng đều
- 11. Số so sánh tìm trung vị của 7 số
- 12. Tính toán kích thước của một mảng
- 13. Kích thước tối đa của vị trí.hash trong trình duyệt
- 14. Điền thuật toán khối lượng
- 15. Chia thùng chứa thành các khối, C++
- 16. Trung bình nhanh mà không có phân chia
- 17. Giải thích thuật toán Median of Medians
- 18. số Chia thành các nhóm có kích thước tương đương
- 19. Google maps API - Bản đồ trung tâm về vị trí hiện tại của khách hàng
- 20. OpenCL kích thước bộ nhớ cục bộ và số đơn vị tính toán
- 21. Thuật toán để lấp đầy các vị trí
- 22. Làm cách nào để có được trung bình (trung bình) của các cột được chọn
- 23. Chỉ nhận các vị trí cho NA chỉ trong "trung tâm" của cột ma trận
- 24. jQuery - Hộp thoại tự động thay đổi kích thước trên nội dung động và duy trì vị trí trung tâm
- 25. Cách tìm vị trí của Thư mục Trung tâm trong một tệp Zip?
- 26. Kích thước/Vị trí của Winforms MDI Client Area
- 27. Độ phức tạp của thuật toán với đầu vào có kích thước cố định
- 28. Vị trí trung tâm dữ liệu Windows Azure ở đâu?
- 29. Đồng vị + Lazyload: kích thước hình ảnh
- 30. Lấy kích thước của các kích thước trong mảng
Điều này chứng tỏ O (n) thời gian chạy của việc sử dụng 20%, nó không bác bỏ các O (n) thời gian chạy của một số tỷ lệ phần trăm khác (nếu một số phần trăm khác cũng là O (n), nó không biện minh cho sự lựa chọn của 20% trên khác). – Dukeling