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),. . | Thiết Kế & Đánh Giá Thuật Toán Phân Tích Đệ Quy TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN Nội Dung Thuậ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) 1 Sắp Xếp Gộp – Mã Giả MergeSort ( , 1, ) 1 if = 1 return 2 MergeSort ( , 1, /2 ) 3 MergeSort ( , /2 + 1, ) 4 Merge ( , 1, /2 , /2 + 1, ) Hàm: Merge Gộp 2 dãy đã sắp xếp làm một ∈ ( ) để gộp phần tử (thời gian tuyến tính) 2 Sắp Xếp Gộp – Phân Tích Thuật Toán MergeSort ( , 1, ) 1 2 3 4 (1) ( /2) ( /2) ( ) if = 1 return MergeSort ( , 1, /2 ) MergeSort ( , /2 + 1, ) Merge ( , 1, /2 , /2 + 1, ) 3 Sắp Xếp Gộp – Phân Tích Thời Gian Thông thường bỏ qua trường hợp cơ bản khi thờ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 = 1 nếu > 1 Tính = 2 /2 + , với hằng số > .
