Hệ thức truy hồi

Hệ thức truy hồi biểu thị thời gian chạy của một thuật toán đệ quy theo thời gian chạy của nó trên các đầu vào nhỏ hơn; việc giải các hệ thức này mang lại các cận tiệm cận dạng đóng được sử dụng để phân tích các thuật toán chia để trị và các thuật toán đệ quy khác.

Definition

Hệ thức truy hồi là một phương trình định nghĩa giá trị của một hàm tại một đầu vào dựa trên các giá trị của nó tại các đầu vào nhỏ hơn; trong phân tích thuật toán, nó biểu thị chi phí của một thuật toán trên một đầu vào có kích thước n theo chi phí của nó trên các bài toán con nhỏ hơn.

Scope

Chủ đề này bao gồm việc xây dựng và giải các hệ thức truy hồi phát sinh trong phân tích thuật toán: phương pháp thế, phương pháp cây đệ quy và định lý Master cho các hệ thức truy hồi chia để trị có dạng T(n) = aT(n/b) + f(n). Nó giải thích cách mỗi thuật toán đệ quy tạo ra một hệ thức truy hồi và cách chuyển đổi hệ thức truy hồi đó thành một cận big-Theta. Nó không bao gồm ký hiệu tiệm cận, được xử lý riêng, và các phương pháp hàm sinh tổ hợp từ toán học rời rạc.

Core questions

• Một thuật toán đệ quy tạo ra một hệ thức truy hồi cho thời gian chạy của nó như thế nào?
• Phương pháp thế được sử dụng như thế nào để chứng minh và kiểm tra một nghiệm phỏng đoán?
• Phương pháp cây đệ quy làm rõ tổng công việc trên các cấp độ đệ quy như thế nào?
• Khi nào định lý Master được áp dụng, và ba trường hợp của nó có ý nghĩa gì?
• Các hệ thức truy hồi không thuộc dạng của định lý Master được xử lý như thế nào?

Key concepts

• hệ thức truy hồi
• phương pháp thế
• phương pháp cây đệ quy
• định lý Master
• hệ thức truy hồi chia để trị
• trường hợp cơ sở và trường hợp đệ quy
• nghiệm dạng đóng
• phương pháp Akra-Bazzi

Key theories

Định lý Master

Đối với các hệ thức truy hồi chia để trị T(n) = aT(n/b) + f(n), định lý Master đưa ra nghiệm tiệm cận bằng cách so sánh f(n) với n lũy thừa log cơ số b của a, bao gồm ba trường hợp khi các lá, gốc, hoặc các cấp độ cân bằng chiếm ưu thế.

Phương pháp cây đệ quy và phương pháp thế

Phương pháp cây đệ quy tổng hợp công việc được thực hiện ở mỗi cấp độ đệ quy để gợi ý một cận, sau đó phương pháp thế chứng minh cận đó một cách chặt chẽ bằng quy nạp; cùng nhau chúng xử lý các hệ thức truy hồi nằm ngoài phạm vi của định lý Master.

Clinical relevance

Giải hệ thức truy hồi là con đường tiêu chuẩn để xác định thời gian chạy của các thuật toán đệ quy, từ mergesort và quicksort đến phép nhân nhanh và nhiều chương trình động. Các kỹ sư và nhà nghiên cứu thường xuyên sử dụng định lý Master để suy ra và chứng minh các tuyên bố về độ phức tạp tiệm cận gắn liền với các thuật toán đó.

History

Phân tích hệ thức truy hồi của các thuật toán đã được hệ thống hóa trong cuốn The Art of Computer Programming của Knuth. Định lý Master trở thành một phần kiến thức cơ bản trong sách giáo khoa thông qua CLRS, và phương pháp Akra-Bazzi (1998) đã tổng quát hóa nó cho một lớp rộng hơn các hệ thức truy hồi chia để trị với các phân chia không đều.

Key figures

• Donald Knuth
• Mohamad Akra
• Louay Bazzi

Seminal works

• cormen2009
• knuth1997vol1

Frequently asked questions

Khi nào tôi có thể sử dụng định lý Master?

Định lý Master áp dụng cho các hệ thức truy hồi có dạng T(n) = aT(n/b) + f(n) với a >= 1 và b > 1, trong đó mỗi cấp độ chia bài toán thành a bài toán con có kích thước n/b. Các hệ thức truy hồi có phân chia không đều, kích thước bài toán con thay đổi, hoặc chi phí kết hợp không phải là đa thức có thể cần đến phương pháp cây đệ quy, phương pháp thế, hoặc phương pháp Akra-Bazzi.

Tại sao hệ thức truy hồi của mergesort lại cho ra O(n log n)?

Mergesort tạo ra T(n) = 2T(n/2) + O(n): hai bài toán con có kích thước bằng một nửa cộng với chi phí hợp nhất tuyến tính. Ở đây, công việc trên mỗi cấp độ là như nhau trên tất cả log n cấp độ của cây đệ quy, vì vậy tổng cộng là n nhân log n, điều mà định lý Master xác nhận là Theta(n log n).