Big O của các phương pháp đệ quy

Question

Tôi đang gặp khó khăn khi xác định O lớn của các phương pháp đệ quy đơn giản. Tôi không thể quấn đầu của tôi xung quanh những gì sẽ xảy ra khi một phương pháp được gọi là nhiều lần. Tôi sẽ cụ thể hơn về các lĩnh vực lẫn lộn, nhưng hiện tại tôi đang cố gắng trả lời một số câu hỏi hw, và thay vì không muốn ăn gian, tôi yêu cầu bất kỳ ai trả lời bài đăng này đều có phương pháp đệ quy đơn giản và cung cấp một lời giải thích đơn giản về phương pháp O lớn của phương pháp đã nói. (Tốt nhất là trong Java ... một ngôn ngữ tôi đang học.)

Cảm ơn bạn.

Answer 1

Bạn cũng có thể xác định thứ tự theo cách đệ quy. Ví dụ, giả sử bạn có hàm f. Để tính f (n) có k bước. Bây giờ bạn muốn tính f (n + 1). Cho phép nói f (n + 1) gọi f (n) một lần, sau đó f (n + 1) mất k + một số bước liên tục. Mỗi lời gọi sẽ mất một số bước liên tục, vì vậy phương thức này là O (n).

Bây giờ hãy xem một ví dụ khác. Nói cho phép bạn thực hiện fibonacci ngây thơ bằng cách thêm hai kết quả theo thời gian:

fib(n) = { return fib(n-1) + fib(n-2) } 

Bây giờ cho phép nói rằng bạn có thể tính toán fib (n-2) và fib (n-1) cả về các bước k. Để tính toán fib (n) bạn cần k + k = 2 * k bước. Bây giờ cho phép nói rằng bạn muốn tính toán fib (n + 1). Vì vậy, bạn cần gấp đôi các bước như đối với fib (n-1). Vì vậy, điều này có vẻ là O (2^N)

Phải thừa nhận rằng, điều này không phải là rất chính thức, nhưng hy vọng theo cách này bạn có thể cảm thấy một chút.

Answer 2

Bạn có thể muốn tham khảo định lý tổng thể để tìm kiếm O lớn của các phương pháp đệ quy. Đây là bài viết wikipedia: http://en.wikipedia.org/wiki/Master_theorem

Bạn muốn nghĩ về một vấn đề đệ quy như một cái cây. Sau đó, hãy xem xét từng cấp độ của cây và lượng công việc cần thiết. Vấn đề thường sẽ rơi vào 3 loại, gốc nặng (lần lặp đầu tiên >> phần còn lại của cây), cân bằng (mỗi cấp có số lượng công việc bằng nhau), lá nặng (last iteration >> phần còn lại của cây).

Đón merge sort là một ví dụ:

define mergeSort(list toSort): 
    if(length of toSort <= 1): 
     return toSort 
    list left = toSort from [0, length of toSort/2) 
    list right = toSort from [length of toSort/2, length of toSort) 
    merge(mergeSort(left), mergeSort(right)) 

Bạn có thể thấy rằng mỗi cuộc gọi của Mergesort lần lượt gọi thêm 2 mergeSorts 1/2 độ dài ban đầu. Chúng tôi biết rằng quy trình hợp nhất sẽ mất thời gian tỷ lệ thuận với số lượng giá trị được hợp nhất.

Mối quan hệ lặp lại sau đó là T (n) = 2 * T (n/2) + O (n). Cả hai đến từ 2 cuộc gọi và n/2 là từ mỗi cuộc gọi chỉ có một nửa số lượng các phần tử. Tuy nhiên, ở mỗi cấp có cùng số phần tử n cần được hợp nhất, do đó công việc liên tục ở mỗi cấp là O (n).

Chúng tôi biết công việc được phân bố đồng đều (O (n) mỗi chiều sâu) và cây là log_2 (n) sâu, do đó, O lớn của hàm đệ quy là O (n * log (n)).