Độ phức tạp của thuật toán với hai cuộc gọi đệ quy

Question

Tôi có một thuật toán lạ hơn được gọi là đệ quy 2 lần. Đó là

int alg(int n) 
    loop body = Θ(3n+1) 
    alg(n-1); 
    alg(n-2) 

Bằng cách nào đó tôi cần phải tìm sự phức tạp của thuật toán này. Tôi đã cố gắng để tìm thấy nó với việc sử dụng đa thức đặc trưng của phương trình trên nhưng hệ thống kết quả là quá khó để giải quyết vì vậy tôi đã tự hỏi nếu có bất kỳ cách thẳng khác ..

Answer 1

Giả định:

1 : n >= 0

2: Θ(3n+1) = 3n + 1

phức tạp:

O(2^n * (3n - 2)); 

Lập luận:

int alg(int n) 
    loop body = Θ(3n+1)// for every n you have O(3n+1) 
    alg(n-1); 
    alg(n-2) 

Giả sử alg không thực hiện cho n < 1, bạn có lặp lại như sau:

Bước n:

3 * n + 1 
alg(n - 1) => 3 * (n - 1) + 1 
alg(n - 2) => 3 * (n - 2) + 1 

Bây giờ bạn về cơ bản có một bộ phận. Bạn phải tưởng tượng một cây số với N là cha mẹ và n-1 và n-2 là trẻ em.

         n 
       n-1         n-2 
      n - 2  n - 3      n - 3  n - 4 
    n - 3 n - 4 n - 4 n - 5    n - 4 n - 5 n - 5 n - 6 
    n-4 n-5 | n-5 n-6 |n-5 n-6 |n-6 n-7 n-5 n-6 n-6 n-7 n-6 n-6| n-6 n-8 

Rõ ràng là có một mẫu lặp lại ở đây. Đối với mỗi cặp (n - k, n - k - 1) in A = {k, with k from 0 to n) trừ hai số đầu tiên và số cuối cùng, (n - 1, n - 2) and (n-2, n-3) có độ phức tạp 3k + 1 * (2^(k - 1)).

Tôi đang xem số lần lặp lại của cặp (n - k, n - k - 1). Vì vậy, ngay bây giờ cho mỗi k từ 0 to n tôi có:

(3k + 1) * (2^(k - 1)) iterations. 

Nếu bạn tổng hợp này lên từ 1 đến n bạn sẽ nhận được kết quả mong muốn. Tôi sẽ mở rộng khái niệm:

(3k + 1) * (2^(k - 1)) = 3k * 2^(k - 1) + 2^(k - 1) 

Cập nhật

1 + 2 + 2^2 + 2^3 + ... + 2^n = 2^(n + 1) - 1 

Trong trường hợp của bạn, đây gió lên hạnh phúc:

2^n - 1 

Dựa trên công thức tổng và k = 0, n . Bây giờ là người đầu tiên:

3k * 2^(k - 1) 

Số tiền này bằng 3 tổng số từ k = 0, n of k * 2^(k - 1). Tổng số đó có thể được xác định bằng cách chuyển sang chức năng chính trị, tích hợp, ký hợp đồng bằng cách sử dụng công thức 1 + a^2 + a^3 + ... + a^n và sau đó phân biệt lại để có được kết quả, là (n - 1) * 2^n + 1.

Vì vậy, bạn có:

2^n - 1 + 3 * (n - 1) * 2^n + 1 

nào ký hợp đồng là:

2^n * (3n - 2); 

Answer 2

phức tạp: alg(n) = Θ(φ^n) nơi φ = Tỷ lệ vàng = (1 + sqrt(5))/2

Tôi không thể chính thức chứng minh điều đó lúc đầu, nhưng với công việc ban đêm, tôi thấy phần thiếu của tôi - Phương pháp thay thế với trừ cụm từ bậc thấp hơn. Xin lỗi vì biểu hiện xấu của tôi về chứng minh (∵ Tiếng Anh nghèo nàn).

---

Hãy loop body = Θ(3n+1) ≦ tn

Giả (đoán) mà cφ^n ≦ alg(n) ≦ dφ^n - 2tn cho một n (n ≧ 4)

Cân nhắc alg(n+1):

 
Θ(n) + alg(n) + alg(n-1) ≦ alg(n+1) ≦ Θ(n) + alg(n)  + alg(n-1) 
    c * φ^n + c * φ^(n-1) ≦ alg(n+1) ≦ tn + dφ^n - 2tn + dφ^(n-1) - 2t(n-1) 
       c * φ^(n+1) ≦ alg(n+1) ≦ tn + d * φ^(n+1) - 4tn + 2 
       c * φ^(n+1) ≦ alg(n+1) ≦ d * φ^(n+1) - 3tn + 2 
       c * φ^(n+1) ≦ alg(n+1) ≦ d * φ^(n+1) - 2t(n+1) (∵ n ≧ 4) 

Vì vậy, nó là chính xác cho n + 1. Bằng cách cảm ứng toán học, chúng ta có thể biết rằng nó chính xác cho tất cả các n.

Vì vậy, cφ^n ≦ alg(n) ≦ dφ^n - 2tn và sau đó alg(n) = Θ(φ^n).

Answer 3

Phần thân của hàm mất Θ(n) thời gian. Chức năng này được gọi hai lần đệ quy.

Đối với các chức năng do sự phức tạp là,

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

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

3 --> T(n-1) = 2T(n-2) + T(n-4) + c  ----- 4 

3-4 -> T(n) = 3T(n-1) - 2T(n-2) - T(n-3) - T(n-4) ----- 5 

Hãy g(n) = 3g(n-1)

Có cho, chúng ta có thể xấp xỉ T(n) = O(g(n))

g (n) là Θ (3 ⁿ)

Có cho T (n) = O (3 ⁿ)

Answer 4

johnchen902 là đúng:

alg(n)=Θ(φ^n) nơi φ = Golden ratio = (1 + sqrt(5))/2

nhưng lập luận của ông là một chút quá tay vẫy, vì vậy chúng ta hãy làm cho nó nghiêm ngặt. Đối số ban đầu của ông là không đầy đủ, do đó tôi đã thêm tôi, nhưng bây giờ là he has completed the argument.

---

loop body = Θ(3n+1) 

Chúng ta hãy biểu thị chi phí của cơ thể loop cho lập luận n với g(n).Sau đó, g(n) ∈ Θ(n) từ Θ(n) = Θ(3n+1).

Hơn nữa, hãy để T(n) là tổng chi phí là alg(n) cho n >= 0. Sau đó, cho n >= 2 chúng ta có tái phát

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

Đối n >= 3, chúng ta có thể chèn tái áp dụng cho T(n-1) vào đó,

T(n) = 2*T(n-2) + T(n-3) + g(n) + g(n-1) 

và cho n > 3, chúng ta có thể tiếp tục, áp dụng tái phát để T(n-2). Đối với đủ lớn n, do đó chúng ta có

T(n) = 3*T(n-3) + 2*T(n-4) + g(n) + g(n-1) + 2*g(n-2) 
    = 5*T(n-4) + 3*T(n-5) + g(n) + g(n-1) + 2*g(n-2) + 3*g(n-3) 
    ... 
             k-1 
    = F(k)*T(n+1-k) + F(k-1)*T(n-k) + ∑ F(j)*g(n+1-j) 
             j=1 

           n-1 
    = F(n)*T(1) + F(n-1)*T(0) + ∑ F(j)*g(n+1-j) 
           j=1 

với những con số Fibonacci F(n) [F(0) = 0, F(1) = F(2) = 1].

T(0) và T(1) là một số hằng số, vì vậy phần đầu tiên rõ ràng là Θ(F(n)). Nó vẫn còn để điều tra tổng.

Kể từ g(n) ∈ Θ(n), chúng ta chỉ cần điều tra

 n-1 
A(n) = ∑ F(j)*(n+1-j) 
     j=1 

Bây giờ,

    n-1 
A(n+1) - A(n) = ∑ F(j) + (((n+1)+1) - ((n+1)-1))*F((n+1)-1) 
       j=1 

       n-1 
       = ∑ F(j) + 2*F(n) 
       j=1 

       = F(n+1) - 1 + 2*F(n) 
       = F(n+2) + F(n) - 1 

Tóm rằng, bắt đầu với A(2) = 2 = F(5) + F(3) - 5, chúng tôi có được

A(n) = F(n+3) + F(n+1) - (n+3) 

và do đó, với

c*n <= g(n) <= d*n 

dự toán

F(n)*T(1) + F(n-1)*T(0) + c*A(n) <= T(n) <= F(n)*T(1) + F(n-1)*T(0) + d*A(n) 

cho n >= 2. Kể từ F(n+1) <= A(n) < F(n+4), tất cả các điều khoản tùy thuộc vào n ở phần bên trái và bên phải của sự bất bình đẳng là Θ(φ^n), q.e.d.