Sử dụng các quan hệ lặp lại để chứng minh một hàm có thời gian chạy theo hàm mũ?

Question

Dưới đây là một chương trình C đơn giản:

int f(int n) { 
    if(n==0 || n==1) { 
    return n; 
    } else { 
    return 2 * f(n - 1) + 3 * f(n - 2); 
    } 
} 

Chương trình này có độ phức tạp thời gian mũ. Bạn có thể thấy điều này trong sơ đồ này của các cuộc gọi chức năng cho f(5):

Tôi muốn chứng minh rằng chức năng có độ phức tạp hàm mũ sử dụng một phương trình tái phát, không phải bằng cách vẽ một sơ đồ và đếm số lượng các chức năng cuộc gọi.

Mối quan hệ tái phát tôi đã đưa ra là

T (n) = T (n-1) + T (n-2) + c

mở rộng cho

T (n) = 2T (n - 2) + T (n - 3) + 2c

Tuy nhiên, tôi không biết cách giải quyết thi s hơn nữa. Làm thế nào tôi có thể giải quyết mối quan hệ tái diễn này?

Answer 1

Đối với người mới bắt đầu, tái phát của bạn cần một số loại trường hợp cơ sở, vì nếu không thì nó không xác định khi bạn nhấn 0. Để đơn giản, giả sử rằng

T (0) = a

T (1) = a + b

T (n + 2) = T (n) + T (n + 1) + c

Hãy bắt đầu mở rộng ra vài thuật ngữ đầu tiên của tái phát này:

• T (0) = a
• T (1) = a + b
• T (2) = 2a + b + c
• T (3) = 3a + 2b + 2c
• T (4) = 5a + 3b + 4c
• T (5) = 8a + 5b + 7c
• T (6) = 13a + 8b + 12c
• T (7) = 21a + 13b + 20c

Có một mô hình rất thú vị đang được định hình ở đây. Hãy xem xét riêng các hệ số của các điều khoản a, b và c. Các hệ số của các điều khoản một theo mô hình

1, 1, 2, 3, 5, 8, 13, 21, ...

Đây là loạt Fibonacci, bù đắp bằng một bước . Hệ số của các thuật ngữ b là

0, 1, 1, 2, 3, 5, 8, 13, ...

Chính xác là chính xác dãy Fibonacci. Cuối cùng, chúng ta hãy nhìn vào các điều khoản c:

0, 0, 1, 2, 4, 7, 12, 20, ...

Hmmm, điều đó không trông quen thuộc. Tuy nhiên, nếu chúng ta đặt nó side-by-side với một điều kiện, chúng tôi thấy điều này:

a: 1, 1, 2, 3, 5, 8, 13, 21, ...

b: 0, 0, 1, 2, 4, 7, 12, 20, ...

Lưu ý rằng các thuật ngữ b là tất cả các cụm từ được trừ ra! Nói cách khác, đó là dãy Fibonacci được dịch chuyển một bước, nhưng với 1 trừ đi từ mỗi kỳ.

Dựa trên những quan sát này, chúng ta có thể phỏng đoán rằng sau đây là đúng:

T (n) = AF _{n + 1} + BF _n + c (F _{n + 1} - 1)

Bây giờ chúng tôi có thể cố gắng chứng minh điều này bằng cảm ứng.Như trường hợp cơ sở của chúng tôi:

T (0) = a = 1a + 0b + 0c = 1a + 0b + (1 - 1) c = AF + BF + c (F -1)

T (1) = a + b = 1a + 1b + 0c = 1a + 1b + (1 - 1) c = AF + BF + c (F - 1)

Đối với bước quy nạp của chúng tôi, chúng ta hãy giả định rằng đối với một số số n tự nhiên, mà

T (n) = AF _{n + 1} + BF _n + c (F _{n + 1}-1)

và

T (n + 1) = AF _{n + 2} + BF _{n + 1} + c (F 0.123.n + 2 - 1)

Sau đó, chúng tôi có mà

T (n + 2) = T (n) + T (n + 1) + c

= AF _{n + 1} + BF _n + c (F _{n + 1}-1) + AF _{n + 2} + BF _{n + 1} + c (F _{n + 2} - 1) + c

= a (F _{n + 1} + F _{n + 2}) + b (F _n + F _{n + 1}) + c (F _{n + 1} + F _{n + 2} - 2 + 1)

= AF _{n + 3} + BF _{n + 2} + c (F _{+ 3 n}-1)

Điều này hoàn thành cảm ứng, vì vậy công thức của chúng tôi phải chính xác!

Vậy điều này liên quan đến hiệu quả như thế nào? Vâng, Binet's formula cho chúng tôi biết rằng F _n = Θ (φ ⁿ), trong đó φ là golden ratio (khoảng 1.61).Điều này có nghĩa rằng

T (n) = AF _{n + 1} + BF _n + c (F _{n + 1}-1) = a Θ (φ ⁿ) + b Θ (φ ⁿ) + c Θ (φ ⁿ) = Θ ((a + b + c) φ ⁿ)

0.123.

Vì vậy, miễn là + b + c ≠ 0, thời gian chạy là Θ (φ ⁿ), là theo cấp số mũ.

Hy vọng điều này sẽ hữu ích!