Một vài ví dụ về thuật toán đệ quy trong tin học

Phần lớn các thuật toán đều dựa trên sự phân rã đệ quy một bài toán lớn thành các bài toán nhỏ, rồi dùng các bài toán nhỏ để giải bài toán ban đầu. Thời gian chạy của thuật toán như thế được xác định bởi kích thước và số lượng các bài toán con. Nên các bài toán đệ quy có thời gian chạy phụ thuộc vào thời gian chạy cho các dữ liệu nhập có kích thước nhỏ hơn, điều này được diễn dịch thành một công thức toán gọi là công thức truy hồi. Do đó, để tính độ phức tạp của thuật toán, ta thường phải giải các phương trình truy hồi. Có nhiều cách như phương pháp thay thế, phương pháp dùng phương trình đặc trưng, .v.v..Bài viết xin giới thiệu vài ví dụ trong phương pháp thay thế.

Ví dụ 1

T1 = 1, Tn = Tn-1 + n với n ≥ 2.

Ví dụ này thường dùng cho các thuật toán đệ quy mà có vòng lặp duyệt qua dữ liệu nhập để giảm bớt một phần tử.

Ta có: Tn = Tn-1 + n = Tn-2 + (n-1) + n = ... = T1 + 2 + 3 + ... + (n-1) + n = n(n+1)/2

Ví dụ 2

T1 = 0, Tn = Tn/2 + 1 với n ≥ 2.

Ví dụ này thường dùng cho các thuật toán đệ quy mà tại mỗi bước chia dữ liệu nhập thành hai phần.

Với n = 2N, ta có Tn = T2N = T2N-1 + 1 =  T2N-2 + 2 = ... = N

Tổng quát, Tn = log2n

Ví dụ 3

T1 = 0, Tn = Tn/2 + n với n ≥ 2.

Ví dụ này thường dùng cho các thuật toán đệ quy mà tại mỗi bước thực hiện, chia đôi dữ liệu nhập nhưng có kiểm tra mỗi phần tử của dữ liệu nhập.

Ta có: Tn = Tn/2 + n = n + n/2 +Tn/4 = ... = n + n/2 + n/4 + ... + T1 ≅ 2n

Ví dụ 4

T1 = 0, Tn = 2Tn/2 + 2n với n ≥ 2.

Ví dụ này thường được dùng cho các thuật toán chia để trị.

Với n = 2N, ta có Tn = T2N = 2T2N-1 + 2N

Chia 2 vế cho 2N ta suy ra: T2/ 2N = T2N-1 / 2N-1 + 1 = T2N-2 / 2N-2 + 2 = ... = N ⇒ T2= N2N

Tổng quát, Tn = n.log2n

1427jpg_310bfaefe44c9ac6f3a0.jpgThuật toán đệ quyQua vài ví dụ trên, hy vọng bạn đọc có thêm minh họa về cách giải thuật toán đệ quy bằng phương pháp thay thế.

(tổng hợp)

Đăng nhập để bình luận
Đang tải thêm ... The comment will be refreshed after 00:00.

Hãy là người đầu tin bình luận về bài viết này!