The running time can be improved by iteratively merging the first with the second, the third with the fourth, and so on[…]. The total running time is therefore in Θ(n log k).
We can further improve upon this algorithm, by iteratively merging the two shortest arrays. It is clear that this minimizes the running time and can therefore not be worse than the strategy described in the previous paragraph. The running time is therefore in O(n log k).[…]
Trong đó: k là số lượng mảng cần merge; n là tổng số phần tử trong k mảng. Ta dùng 2-way merge để merge hai mảng bất kỳ.
Anh nào đã học qua thuật toán này giải thích cho em với ạ! Vì sao khi liên tục(iteratively) merge hai mảng nhỏ nhất lại cho thời gian chạy tốt hơn khi liên tục merge mảng 1 với mảng 2; mảng 3 với mảng 4;… ?
Nếu em hiểu đúng thì phiên bản “tốt hơn” sẽ merge hai mảng nhỏ nhất trong k mảng thành một mảng. Lúc này, ta có (k-1) mảng. Thuật toán lặp lại điều trên cho tới khi merge xong. Ví dụ như trong trường hợp k=4:
Phiên bản đầu sẽ di chuyển dữ liệu tổng cộng log_2(4).n = 2n (lần)
Phiên bản thứ hai thì đếm như sau:
Giả sử: a1, a2, a3, a4 là số phần tử của 4 mảng.
Sau khi merge lần 1: a1’; a2’; a3’
Sau khi merge lần 2: a1’’; a2’’
Lần cuối: a1’’’
Trong đó: a1’, a1’’, a1’’’ bằng tổng số phần tử của 2 mảng nhỏ nhất; những giá trị còn lại là những phần tử không được merge ở đầu mỗi lần merge
Vì lúc nào tổng số phần tử của tất cả cũng là n. Cho nên: Tổng số lần di chuyển dữ liệu là:
a1’ + a1’’ + a1’’’ = n - ( a2’ + a3’) + n - (a2’’) + n = 2n + n - (a2’ + a3’ + a2’’) = 2n + a1’ - a2’’ <= 2n
Thật vậy:
Nếu a1’ = a2’’, nghĩa là a1’ lớn nhất trong (a1’, a2’, a3’) (vì thuật toán chỉ merge hai mảng nhỏ nhất), thì a1’ - a2’’ = 0
Ngược lại, a2’ hoặc a3’ lớn nhất cho nên: a2’’ bằng một trong hai và lớn hơn a1’.
Cho nên, kết luận: Phiên bản thứ hai tốt hơn với k=4
Em chỉ chứng minh được một trường hợp này thôi. Nhưng nếu tổng quát lên thì hiểu vấn đề này như thế nào ạ? Em cảm ơn.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?