Bài giảng Thuật toán (Algorithms)
Giả sử rằng, thuật toán phân chia một bài toán cỡ n thành a bài toán nhỏ. Trong đó mỗi bài toán nhỏ có cỡ n/b.
Cũng vậy, ta giả sử rằng tổng các phép toán thêm vào khi thực hiện phân chia và tổng hợp lời giải của bài toán là g(n).
Khi đó nếu f(n) là số các phép toán cần thiết để giải bài toán đã cho, thì f thỏa mãn hệ thức truy hồi sau đây:
F(n) = a.f(n/b) +g(n).
Bài giảng Thuật toán (Algorithms) trang 1
Bài giảng Thuật toán (Algorithms) trang 2
Bài giảng Thuật toán (Algorithms) trang 3
Bài giảng Thuật toán (Algorithms) trang 4
Bài giảng Thuật toán (Algorithms) trang 5
Tải về để xem đầy đủ hơn
File đính kèm:
bai_giang_thuat_toan_algorithms.ppt
