Bài giảng gồm các bài tập áp dụng Chia để trị có hướng dẫn chi tiết phương pháp làm nhằm giúp các bạn hiểu rõ hơn về thuật toán này. Tài liệu tham khảo hữu ích dành cho các bạn ngành Công nghệ thông tin. . | 2/2/2017 Phân tích và Thiết kế THUẬT TOÁN Hà Đại Dương duonghd@ Web: Bài 5 - Chia để trị (tiếp) PHÂN TÍCH VÀ THIẾT KẾ THUẬ TOÁN NỘI DUNG I. II. III. IV. Giới thiệu Lược đồ chung Bài toán áp dụng 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 Và z x * y (a *10n /2 b)(c *10n /2 d ) y c * 10 n / 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 5. Nhân số nguyên (lớn) Thuật .
