Bài giảng Thiết kế và đánh giá thuật toán: Phân tích đệ quy - TS. Lê Nguyên Khôi

Bài giảng "Thiết kế và đánh giá thuật toán: Phân tích đệ quy" cung cấp cho người học các kiến thức: Thuật toán đệ quy, phân tích toán học (mathematical tool), thay thế(substitution), cây đệ quy (recurrence tree),... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Thiết kế và đánh giá thuật toán: Phân tích đệ quy - TS. Lê Nguyên KhôiThiết Kế & Đánh Giá Thuật ToánPhân Tích Đệ QuyTS. Lê Nguyên KhôiTrường Đại Học Công Nghệ - ĐHQGHNNội DungThuật toán đệ quy Phương pháp:Phân tích toán học (mathematical tool) Thay thế (substitution) Cây đệ quy (recurrence tree) Định lý tổng quát (master theorem)1Sắp Xếp Gộp – Mã GiảMergeSort (, 1, )1if = 1 return2MergeSort (, 1, /2 )3MergeSort (, /2 + 1, )4Merge (, 1, /2 , /2 + 1, )Hàm: MergeGộp 2 dãy đã sắp xếp làm một ∈ () để gộp phần tử (thời gian tuyến tính)2Sắp Xếp Gộp – Phân Tích Thuật ToánMergeSort (, 1, )1234(1)(/2)(/2)()if = 1 returnMergeSort (, 1, /2 )MergeSort (, /2 + 1, )Merge (, 1, /2 , /2 + 1, )3Sắp Xếp Gộp – Phân Tích Thời GianThông thường bỏ qua trường hợp cơ bản khithời gian chạy nhỏ, nhưng chỉ khi không làmảnh hưởng đến kết quả của tiệm cận 1 =2 /2 + nếu = 1nếu > 1Tính = 2 /2 + , với hằng số > 04