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

Thiết Kế & Đánh Giá Thuật Toán<br /> Phân Tích Đệ Quy<br /> TS. Lê Nguyên Khôi<br /> Trường Đại Học Công Nghệ - ĐHQGHN<br /> <br /> Nội Dung<br /> Thuật toán đệ quy<br />
Phương pháp:<br />
<br /> <br /> Phân tích toán học (mathematical tool)<br />
Thay thế (substitution)<br />
Cây đệ quy (recurrence tree)<br />
Định lý tổng quát (master theorem)<br />
<br /> <br /> 1<br /> <br /> Sắp Xếp Gộp – Mã Giả<br /> MergeSort (, 1, )<br /> 1<br /> if  = 1 return<br /> 2<br /> MergeSort (, 1, /2 )<br /> 3<br /> MergeSort (, /2 + 1, )<br /> 4<br /> Merge (, 1, /2 , /2 + 1, )<br />
<br /> <br /> Hàm: Merge<br />
<br />
<br /> <br /> Gộp 2 dãy đã sắp xếp làm một<br />   ∈ <br /> () để gộp  phần tử (thời gian tuyến tính)<br /> <br /> 2<br /> <br /> Sắp Xếp Gộp – Phân Tích Thuật Toán<br /> MergeSort (, 1, )<br /> 1<br /> 2<br /> 3<br /> 4<br /> <br /> (1)<br /> (/2)<br /> (/2)<br /> ()<br /> <br /> if  = 1 return<br /> MergeSort (, 1, /2 )<br /> MergeSort (, /2 + 1, )<br /> Merge (, 1, /2 , /2 + 1, )<br /> <br /> 3<br /> <br /> Sắp Xếp Gộp – Phân Tích Thời Gian<br />
<br /> <br /> Thông thường bỏ qua trường hợp cơ bản khi<br /> thời gian chạy nhỏ, nhưng chỉ khi không làm<br /> ảnh hưởng đến kết quả của tiệm cận<br /> <br /> 1 <br />   =<br /> 2 /2 + <br /> <br /> <br /> nếu  = 1<br /> nếu  > 1<br /> <br /> Tính   = 2 /2 + , với hằng số  > 0<br /> <br /> 4<br /> <br />