Tại sao việc sử dụng thuật toán sắp xếp dựa trên so sánh (Comparison-based sorting) như Merge Sort lại không thể đạt được độ phức tạp thời gian tốt hơn O(n log n) trong trường hợp xấu nhất?

Question

Accepted Answer

Theo lý thuyết thông tin và cây quyết định (Decision Tree Model), bất kỳ thuật toán sắp xếp nào dựa trên việc so sánh các phần tử đều có thể được biểu diễn dưới dạng một cây nhị phân. Trong đó, mỗi nút lá đại diện cho một hoán vị có thể xảy ra của mảng đầu vào.
Phân tích:

Với một mảng có n phần tử, có n! (n giai thừa) hoán vị khác nhau.
Một cây nhị phân với n! lá sẽ có chiều cao tối thiểu là log2(n!).
Theo công thức xấp xỉ Stirling, log2(n!) xấp xỉ n log2(n).
Do đó, chiều cao của cây quyết định - tương ứng với số lần so sánh tối thiểu trong trường hợp xấu nhất - luôn bị chặn dưới bởi O(n log n).

Kết luận: Để vượt qua giới hạn O(n log n), chúng ta phải sử dụng các thuật toán không dựa trên so sánh (Non-comparison sorting) như Counting Sort, Radix Sort hoặc Bucket Sort, với điều kiện dữ liệu đầu vào phải có các đặc tính cụ thể (ví dụ: là số nguyên trong một phạm vi nhất định).

Tại sao việc sử dụng thuật toán sắp xếp dựa trên so sánh (Comparison-based sorting) như Merge Sort lại không thể đạt được độ phức tạp thời gian tốt hơn O(n log n) trong trường hợp xấu nhất?

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi sorting liên quan cùng chủ đề