quicksort và chèn sắp xếp lai dự kiến ​​thời gian chạy

Question

Tôi tự học CLRS phiên bản thứ 3 và đây là một trong những câu hỏi khó khăn hơn mà tôi đã gặp phải cùng với câu trả lời của nó như một dịch vụ cho tất cả.

7.4-5 Chúng tôi có thể cải thiện thời gian chạy của quicksort trong thực tế bằng cách tận dụng thời gian nhanh hoạt động của sắp xếp chèn khi đầu vào của nó là “gần” được sắp xếp. Khi gọi số quicksort trên một subarray có ít hơn k yếu tố, hãy để nó đơn giản quay trở lại mà không cần sắp xếp subarray. Sau khi cuộc gọi cấp cao nhất để trả về quicksort, hãy chạy sắp xếp chèn trên toàn bộ mảng để hoàn thành quá trình sắp xếp. Cho rằng thuật toán sắp xếp này chạy trong O(nk+nlg(n/k)) thời gian dự kiến. Làm thế nào chúng ta nên chọn k, cả về lý thuyết và trong thực tế?

Answer 1

Nếu bạn đánh giá phương trình nlgn > nk + nlog(n/k) bạn nhận được log k > k. Điều đó là không thể được. Do đó trong lý thuyết nó không thể. Nhưng trong thực tế có những yếu tố liên quan liên quan đến việc sắp xếp chèn và quicksort. Hãy xem giải pháp được thảo luận trong số pdf này. Bạn có thể muốn cập nhật câu trả lời của mình. .

Answer 2

Một chiếc lá có xác suất bằng nhau có kích thước từ 1 đến k.
Vì vậy, kích thước mong đợi của một chiếc lá là k/2.
Nếu kích thước mong đợi của một chiếc lá là k/2 thì chúng tôi mong đợi n/(k/2)=(2n)/k những chiếc lá như vậy.
Để đơn giản, hãy nói rằng chúng tôi mong đợi n/k những chiếc lá như vậy và kích thước mong đợi của mỗi chiếc lá là k.
Thời gian chạy dự kiến ​​là INSERTION-SORT là O(n^2).
Chúng tôi thấy rằng trong bài tập 5.2-5 và bài toán 2-4c.
Vì vậy, thời gian chạy dự kiến ​​của INSERTION-SORT cách sử dụng là O((n/k)*(k^2))=O(nk).
Nếu chúng tôi mong đợi các nhóm phân vùng của chúng tôi có kích thước k thì chiều cao của cây đệ quy dự kiến ​​là lgn-lgk=lg(n/k) vì chúng tôi dự kiến ​​sẽ dừng lgk trước đó.
Có hoạt động O(n) trên mỗi cấp độ của cây đệ quy.
Điều đó dẫn chúng tôi đến O(nlg(n/k)).
Chúng tôi kết luận rằng thời gian chạy dự kiến ​​là O(nk+nlg(n/k)).

Về lý thuyết, chúng ta nên chọn k=lgn, vì cách này chúng tôi có thời gian chạy được mong đợi tốt nhất là O(nlgn).

Trong thực tế, chúng ta nên chọn k cho một trong các giá trị xung quanh lgn cho chúng ta hiệu suất tốt hơn so với chỉ chạy RANDOMIZED-QUICKSORT.

Phần thứ hai của câu trả lời sử dụng ký hiệu big-O khá lỏng lẻo, do đó, để chọn chính xác hơn k, vui lòng theo liên kết được đưa ra trong câu trả lời thứ hai của Ankush.

Answer 3

Thực ra, câu trả lời là k = 8.

Thuật toán bạn nhận được là thành phần của hai chức năng ẩn danh, một trong số đó là O(nk) và khác là O(n lg n/k). Những hàm ẩn danh này ẩn các hằng số trường hợp trung bình. Sắp xếp chèn chạy trong thời gian trung bình n^2/4 và trường hợp nhanh được phân ngẫu nhiên trong trường hợp trung bình là 1.386 n lg n. Chúng tôi muốn tìm giá trị k giúp giảm thiểu giá trị của nk/4 + 1.386(n lg n/k) tương đương với nk/4 + 1.386 n lg n - 1.386 n lg k. Điều này có nghĩa là tìm tối đa chức năng 1.386 lg k - k/4. Giá trị tối đa đó xảy ra tại k = 8.