Thuật toán đệ quy là gì? Và cách tính độ phức tạp của thuật toán đệ quy như thế nào? Bài viết dưới đây sẽ phần nào giúp bạn giải quyết các câu hỏi trên. Cùng bắt đầu đi tìm hiểu luôn nhé.
Thuật toán đệ quy là gì?
Đệ quy (Recursion) là một trong những giải thuật quen thuộc trong lập trình, hay rộng hơn là trong toán học (thường được gọi với cái tên khác là “quy nạp”). Có một số bài toán, bắt buộc người giải phải sử dụng đệ quy mới giải quyết được, chẳng hạn như duyệt cây.
Mô tả đệ quy được hiểu là một đối tượng được mô tả thông qua chính nó.
Một bài toán mang tính chất đệ quy khi nó có thể được phân ra thành các bài toán nhỏ hơn nhưng vẫn mang cùng tính chất với bài toán ban đầu. Các bài toán nhỏ lại được phân ra thành các bài toán nhỏ hơn nữa theo cùng như tính chất đó.
Cách tính độ phức tạp của thuật toán đệ quy
Cách tính độ phức tạp của thuật toán đệ quy hay bất kì một thuật toán nào cũng là một vấn đề không hề đơn giản. Tuy nhiên, bạn đều có thể tuân theo một số nguyên tắc sau:
Quy tắc bỏ qua hằng số
Giả sử một đoạn chương trình P có thời gian thực hiện là T(n) = O(c1.f(n)) với c1 là một hằng số dương thì ta có thể coi đoạn chương trình đó có độ phức tạp tính toán là O(f(n)) tức là ta bỏ qua hằng số.
Quy tắc cộng – lấy max
Giả sử hai đoạn chương trình P1 và P2 có thời gian thực hiện lần lượt là T1(n) và T2(n). Và T1(n)=O(f(n)), T2(n)=O(g(n)) thì ta có thời gian thực hiện của đoạn hai đoạn chương trình đó nối tiếp nhau sẽ là T(n)=O(max(f(n),g(n)))
Quy tắc nhân
Nếu hai đoạn chương trình P1 và P2 có thời gian thực hiện lần lượt là T1(n) và T2(n). Và T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của đoạn hai đoạn chương trình đó lồng nhau sẽ là T(n) = O(f(n).g(n))
Quy tắc tổng quát để phân tích một chương trình
- Thời gian thực hiện mỗi lệnh gán, READ, WRITE là O(1).
- Thời gian thực hiện một chuỗi tuần tự các lệnh được tính bằng quy tắc cộng. Như vậy thời gian này chính là thời gian thi hành của một lệnh nào đó lâu nhất trong chuỗi lệnh.
- Thời gian thực hiện cấu trúc IF là thời gian chiếm lớn nhất thực hiện lệnh sau THEN hoặc sau ELSE và thời gian kiểm tra điều kiện. Thường thời gian kiểm tra điều kiện sẽ là O(1).
- Thời gian thực hiện vòng lặp là tổng (trên tất cả các lần lặp) thời gian thực hiện thân của vòng lặp đó. Nếu thời gian thực hiện thân vòng lặp không thay đổi thì thời gian thực hiện vòng lặp là tích của số lần lặp nhân với thời gian thực hiện thân vòng lặp.
Ðộ phức tạp của chương trình có gọi chương trình con không đệ quy
Giả sử như ta đang có một chương trình với các chương trình con không đệ quy, vậy để tính thời gian thực hiện của chương trình, đầu tiên chúng ta cần tính thời gian thực hiện của các chương trình con không đệ quy (không gọi các chương trình con khác).
Tiếp đó, ta sẽ đi tính thời gian thực hiện của các chương trình con chỉ gọi các chương trình con mà đã tính được thời gian thực hiện của chúng. Sau đó, chúng ta sẽ tiếp tục quá trình đánh giá thời gian thực hiện của mỗi chương trình con sau khi hoàn tất việc đánh giá thời gian thực hiện của tất cả các chương trình con mà nó gọi. Cuối cùng là tính thời gian thực hiện cho chương trình chính.
Phân tích các chương trình Ðệ quy
Với các chương trình có gọi các chương trình con đệ quy (có gọi các chương trình con khác), trước hết ta cần phải lập các phương trình đệ quy, sau đó cần đi giải phương trình đệ quy, nghiệm của phương trình đệ quy đó chính là thời gian thực hiện của chương trình đệ quy cần tính.
Thành lập phương trình đệ quy
Phương trình đệ quy là một phương trình biểu diễn mối liên hệ giữa thời gian thực hiện chương trình với kích thước dữ liệu nhập n (được gọi là T(n)) và thời gian thực hiện chương trình với kích thước dữ liệu nhập k (được gọi là T(k)), với k < n.
Ðể thành lập được phương trình đệ quy, chúng ta phải căn cứ vào chương trình đệ quy. Thông thường, một chương trình đệ quy để giải bài toán kích thước n, bắt buộc phải có ít nhất một trường hợp dừng tương ứng với một n cụ thể và lời gọi đệ quy để giải bài toán kích thước k (k0) phải gọi đệ quy Giai_thua(n-1). Việc gọi đệ quy này tốn T(n-1) thời gian.
Sau khi hoàn thành việc gọi đệ quy, chương trình phải nhân kết quả tìm được với n và gán cho Giai_thua. Thời gian để thực hiện phép nhân và phép gán là một hằng số C2. Ta có:
Ðây chính là phương trình đệ quy để tính thời gian thực hiện của chương trình đệ quy Giai_thua.
Cách giải phương trình đệ quy
Phương pháp truy hồi:
Dùng đệ quy để thay thế bất kỳ T(m) với m<n vào vế phải của phương trình cho đến khi nào m=1.
Phương pháp tổng quát
Chia bài toán thành các bài toán con và mỗi bài toán có kích thước n/b. Và cứ như thế chia cho đến khi bài toán đủ nhỏ để giải quyết.
Trên đây là một số chia sẻ về thuật toán đệ quy và cách tính độ phức tạp của thuật toán đệ quy. Hy vọng rằng những chia sẻ ở trên sẽ có thể giúp ích cho bạn trong quá trình học lập trình.