tailieunhanh - Bài giảng Phân tích và thiết kế thuật toán: Bài 5 - Hà Đại Dương

"Bài giảng Phân tích và thiết kế thuật toán - Bài 5: Chia để trị" thông qua bài học này người học nắm chắc kiến thức về lược đồ chung và bài toán áp dụng của chia để trị; nhân số nguyên (lớn), nhân ma trận, dãy con lớn nhất, tính lũy thừa, hoán đổi phần tử của mảng. | 2 2 2017 Phân tích và Thiết kế THUẬT TOÁN Hà Đại Dương duonghd@ Web duonghd Bài 5 - Chia để trị tiếp PHÂN TÍCH VÀ THIẾT KẾ THUẬ TOÁN NỘI DUNG I. Giới thiệu II. Lược đồ chung III. Bài toán áp dụng IV. Bài tập 1 2 2 2017 III. Bài toán áp dụng 5. Nhân số nguyên lớn Bài toán Nhân 2 số nguyên lớn x y có n chữ số x x n 1 x n 2 .x1 x0 y y n 1 y n 2 . y1 y 0 z x y z 2 n 1 z 2 n 2 .z1 z 0 Quá quen Đến mức không cần phải thắc mắc về tính tối ưu của nó Cách thức vẫn làm quá quen Độ phức tạp O n2 III. Bài toán áp dụng 5. Nhân số nguyên lớn Ý tưởng Chia để trị Đặt a x n 1 x n 2 .x n 2 b x n 2 1 x n 2 2 .x 0 c y n 1 y n 2 . y n 2 d y n 2 1 y n 2 2 . y 0 Khi đó x a 10 n 2 b y c 10 n 2 d Và z x y a 10n 2 b c 10n 2 d a c 10n a d b c 10n 2 b d III. Bài toán áp dụng 5. Nhân số nguyên lớn Ý tưởng Chia để trị x y có độ dài bằng nhau và độ dài có dạng 2m nếu Có 1 chữ số làm trực tiếp Có n chữ số Tích của nó có thể biểu diễn qua tích của 4 số nguyên có độ dài n 2 chữ số z a c 10n a d b c 10n 2 b d và các phép cộng dịch phải 2 2 2 2017 III. Bài toán áp dụng 5. Nhân số nguyên lớn Ý tưởng Chia để trị z a c 10n a d b c 10n 2 b d Gọi T n là thời gian thực hiện phép nhân 2 số nguyên có độ dài n thì T n 4T n 2 O n O n là thời gian thực hiện các phép cộng và dịch phải Giải công thức truy hồi trên ta được T n O n 2 Chưa nhanh hơn nếu không chia để trị III. Bài toán áp dụng 5. Nhân số nguyên lớn Ý tưởng Năm 1962 nhà toán học người Nga Anatoly Alexeevitch Karatsuba Karatsuba đã tối ưu thời gian thực hiện phép nhận 2 số nguyên có n chữ số như sau Khi đó T n 3T n 2 O n Giải phương trình đệ qui ta được T n O nlog23 O III. Bài toán áp dụng Karatsuba x y n 5. Nhân số nguyên lớn Thuật toán Karatsuba If n 1 Return x y Else a x n-1 . . . x n 2 b x n 2-1 . . . x 0 c y n-1 . . . y n 2 d y n 2-1 . . . y 0 U Karatsuba a c n 2 V Karasuba b d n 2 W Karatsuba a b c d n 2 Return U 10n W-U-V 10n 2 V 3 2 2 2017 III. Bài toán áp dụng 6. Nhân ma trận III. Bài toán áp dụng 6. Nhân ma .