Bài giảng Thiết kế và Phân tích thuật toán_Chương 4: Phương pháp chia để trị
Chia để trị là một kỹ thuật thiết kế thuật toán bao gồm việc chia một bài toán cần giải ra thành những bài toán con nhỏ hơn có cùng một loại vấn đề, giải từng bài toán con đó một cách lần lượt và độc lập, sau đó kết hợp các lời giải con thu được nhờ cách đó để thu được lời giải của bài toán nguyên thủy. Hai câu hỏi tự nhiên xảy ra là "Vì sao ai đó làm việc này?" và "Chúng ta cần giải các bài toán con như thế này?". Tính hiệu quả của thuật chia để trị nằm ở câu trả lời cho câu hỏi thứ hai.
Bạn đang xem trước 20 trang tài liệu Bài giảng Thiết kế và Phân tích thuật toán_Chương 4: Phương pháp chia để trị, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Hiệu quả của thuật toán: T(n)=O(logn) Thuật toán tìm kiếm nhị phân đưa bài toán tìm kiếm cỡ n về bài toán tìm kiếm phần tử này trong dãy tìm kiếm cỡ n/2, khi n chẵn. Khi thực hiện việc rút gọn cần hai phép so sánh. Vì thế, nếu f(n) là số phép so sánh cần phải làm khi tìm kiếm một phần tử trong danh sách tìm kiếm cỡ n ta có f(n) = f(n/2) + 2, nếu n là số chẵn. tăng
