L'utilizzo delle relazioni di ricorrenza per dimostrare una funzione ha un runtime esponenziale?

Question

Ecco un semplice programma C:

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

Questo programma presenta esponenziale tempo la complessità. Si può vedere questo in questo diagramma delle chiamate di funzione per f(5):

voglio dimostrare che la funzione ha complessità esponenziale usando un'equazione di ricorrenza solo, non disegnando un diagramma e contando il numero di funzione chiamate.

La relazione di ricorrenza ho fornito è

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

espandentesi dà

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

Tuttavia, non so come risolvere thi s ulteriormente. Come posso risolvere questa relazione di ricorrenza?

Answer 1

Per cominciare, la vostra ricorrenza ha bisogno di un qualche tipo di scenario di base, in quanto altrimenti è indefinito quando si colpisce 0. Per semplicità, diciamo che

T (0) = a

T (1) = a + b

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

Iniziamo espandendo i primi termini della presente ricorrenza:

• 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'è uno schema molto interessante che prende forma qui. Esaminiamo individualmente i coefficienti dei termini a, b e c. I coefficienti dei termini a seguire lo schema

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

Questa è la serie di Fibonacci, compensata da un passo . I coefficienti dei termini b sono

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

Quale è esattamente la serie di Fibonacci. Infine, diamo un'occhiata ai termini C:

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

Hmmm, che non sembra familiare. Tuttavia, se lo mettiamo fianco a fianco con i un termini, vediamo questo:

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

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

noti che i termini b sono tutti i termini con un unico sottratto fuori! In altre parole, è la serie di Fibonacci spostata di un passo, ma con 1 sottratto da ogni termine.

Sulla base di queste osservazioni, possiamo ipotizzare che quanto segue è vero:

T (n) = aF _{n + 1} + bF _n + c (F _{n + 1} - 1)

Ora possiamo provare a provarlo per induzione.Come i nostri casi di base:

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)

Per il nostro passo induttivo, supponiamo che per qualche numero naturale n, che

T (n) = aF _{n + 1} + bF _n + c (F _{n + 1} - 1)

e che

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

allora abbiamo che

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 _{n + 3} - 1)

Questo completa l'induzione, quindi la nostra formula deve essere corretta!

Quindi, come si collega all'efficienza? Beh, Binet's formula ci dice che F _n = Θ (φ ⁿ), dove φ è la golden ratio (circa 1,61).Ciò significa che

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

0.123.

Quindi, fintanto che a + b + c ≠ 0, il runtime è Θ (φ ⁿ), che è esponenziale.

Spero che questo aiuti!