Tại sao các yếu tố liên tục của quicksort tốt hơn so với heapsort?

Question

Theo tính toán của tôi:

• Sắp xếp nhanh chi phí = n + (n/2 + n/2) + (n/4 + n/4 + n/4 + n/4) + ... = n * log (n) = log (n ⁿ)
• Chi phí heapsort = tổng [log (i)] cho i = n, n-1, n-2, ..., 1 = log (n!)

Tại sao nó được cho biết quicksort có yếu tố không đổi tốt hơn so với heapsort và do đó sắp xếp nhanh là tốt hơn so với heapsort ở mức trung bình? Không phải là nhật ký (n ⁿ)> nhật ký (n!)?

Answer 1

Tôi nghĩ rằng vấn đề ở đây là phân tích của bạn về quicksort và heapsort không đủ chính xác để cho thấy lý do tại sao các yếu tố không đổi sẽ khác nhau.

Bạn thực sự có thể cho thấy rằng trung bình, quicksort sẽ làm được nhiều hơn so sánh hơn sắp xếp vun đống (khoảng 1,44 n log n cho quicksort so n log n so với sắp xếp vun đống). Tuy nhiên, so sánh không phải là yếu tố quyết định duy nhất trong thời gian chạy của heapsort và quicksort.

Lý do chính nhanh hơn nhanh hơn là locality of reference. Do cách bộ nhớ lưu trữ hoạt động, việc truy cập mảng ở các vị trí liền kề với nhau có xu hướng nhanh hơn nhiều, nhanh hơn nhiều so với các truy cập mảng nằm rải rác trong một mảng. Trong quicksort, bước phân vùng thường thực hiện tất cả các lần đọc và ghi của nó ở cuối các mảng, do đó các truy cập mảng được đóng gói chặt chẽ với nhau. Heapsort, mặt khác, nhảy xung quanh mảng khi nó di chuyển lên và xuống đống. Vì vậy, mảng truy cập trong quicksort, trung bình, mất ít thời gian hơn nhiều so với mảng truy cập trong heapsort. Sự khác biệt là đủ lớn để hệ số không đổi ở phía trước của n log n trong quicksort thấp hơn hệ số không đổi trước chữ n log n trong heapsort, đó là một lý do tại sao quicksort nhanh hơn nhiều so với heapsort.

Tóm lại - nếu tất cả những gì chúng tôi quan tâm là so sánh, heapsort là lựa chọn tốt hơn so với quicksort. Nhưng kể từ khi hệ thống bộ nhớ sử dụng cache và bộ nhớ cache bỏ lỡ là tốn kém, quicksort thường là một lựa chọn tốt hơn nhiều.

Ngoài ra, lưu ý rằng log (n ⁿ) = n log n và log (n!) = N log n - n + O (log n) thông qua Stirling's approximation. Điều này có nghĩa là nhật ký (n!) Không nhỏ hơn nhiều so với n log n, ngay cả khi n rất lớn. Có chắc chắn là một sự khác biệt, nhưng nó không đủ lớn để làm cho một vết lõm lớn trên riêng của mình.

Hy vọng điều này sẽ hữu ích!

Answer 2

Dưới đây là đoạn từ tay Các Thuật toán thiết kế Steven S. Skiena, mà nói về tốc độ giữa ba (nlogn) sắp xếp algortihms O:

Nhưng làm thế nào chúng ta có thể so sánh hai Θ (n log n) các thuật toán để quyết định nhanh hơn ? Làm thế nào chúng ta có thể chứng minh rằng quicksort thực sự nhanh chóng? Thật không may, mô hình RAM và phân tích Big Oh cung cấp một bộ công cụ quá thô đến làm cho loại phân biệt đó. Khi phải đối mặt với các thuật toán của cùng một sự phức tạp tiệm cận , chi tiết triển khai và hệ thống quirks như vậy như hiệu suất bộ nhớ cache và kích thước bộ nhớ cũng có thể chứng minh được yếu tố quyết định .

gì chúng ta có thể nói là thí nghiệm cho thấy nơi một quicksort thực hiện đúng được thực hiện tốt, nó là nhanh hơn mergesort hoặc sắp xếp vun đống thường 2-3 lần. Lý do chính là rằng các hoạt động trong vòng lặp bên trong đơn giản hơn. Nhưng tôi không thể tranh luận với bạn nếu bạn không tin tôi khi tôi nói quicksort nhanh hơn. Đó là câu hỏi có giải pháp nằm ngoài các công cụ phân tích mà chúng tôi đang sử dụng. Cách tốt nhất để nói là triển khai cả hai thuật toán và thử nghiệm .

-4.6.3 "Is Sắp xếp nhanh Thật nhanh?", Các thiết kế thuật toán Manual