Khi áp dụng Divide and Conquer để giải quyết bài toán đếm số lượng nghịch thế (Inversion Count) trong mảng, tại sao việc kết hợp với Merge Sort lại mang lại hiệu quả vượt trội?

Question

Accepted Answer

Bài toán đếm nghịch thế yêu cầu tìm số cặp (i, j) sao cho i < j và A[i] > A[j]. Khi sử dụng Merge Sort, trong quá trình trộn (merge) hai mảng con đã sắp xếp, nếu phần tử ở mảng bên phải nhỏ hơn phần tử ở mảng bên trái, ta biết ngay rằng phần tử đó nhỏ hơn tất cả các phần tử còn lại trong mảng bên trái. Điều này cho phép đếm số lượng nghịch thế trong thời gian O(n log n) thay vì O(n^2) bằng cách duyệt trâu bò.

Khi áp dụng Divide and Conquer để giải quyết bài toán đếm số lượng nghịch thế (Inversion Count) trong mảng, tại sao việc kết hợp với Merge Sort lại mang lại hiệu quả vượt trội?

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 divide & conquer liên quan cùng chủ đề