[Algoritmi] Ricorrenze

Messaggioda FurioShow » 16/11/2018, 19:55

Salve ragazzi, sto studiando le ricorrenze ed ho dei dubbi riguardo 2 metodi:albero di ricorsione e sostituzione.
Ho questa ricorrenza:
$T(n)={ ( 1 ),( T(n/2)+2T(n/4)+n ):}$ Primo caso se n=0,1 Secondo caso n>1.
Se sviluppo l'albero mi ritrovo per ogni livello $3^i$ nodi, però ad esempio per il livello 1, ho 2 nodi che sono $cn/4$ ed uno $cn/2$, quindi non so come gestire questa situazione per calcolare poi i livelli di tale albero e quindi ipotizzare una soluzione per utilizzare il metodo di sostituzione.
Inoltre ho un'altra domanda per il metodo iterativo nel caso, come questo, ci siano 2 o più chiamate interne, vanno sviluppate separatamente in modo da calcolarsi il limite inferiore e superiore?
Ultima modifica di FurioShow il 17/11/2018, 15:44, modificato 1 volta in totale.
FurioShow
New Member
New Member
 
Messaggio: 27 di 60
Iscritto il: 28/09/2017, 15:55

Re: [Algoritmi] Ricorrenze

Messaggioda Quinzio » 17/11/2018, 11:33

Non mi sembra un esercizio banale, l'unica cosa che si vede e' questa:

$T(n) = $

$T(n/2)+ T(n/4) + n$
e adesso scompongo solo $T(n/2)$

$2T(n/4) +T(n/8) + n + n/2$
e qui scompongo solo $T(n/4)$

$3T(n/8) +2T(n/16) + n + n/2 + 2n/4$

$5T(n/16) +3T(n/32) + n + n/2 + 2n/4 + 3n/8$

$Fib(log(n)) + kn $

A sinistra si vede la sequenza di Fibonacci, a destra c'e' qualcosa che non cresce molto rapidamente.
Secondo me oltre a questo risultato non si va.
Come dici tu non vengono date informazioni su cosa fare con termini come $T(k), k<1$, ad es $T(1/2)$.
Si puo' supporre di considerarli tutti uguali a 1.
Quinzio
Cannot live without
Cannot live without
 
Messaggio: 4114 di 10487
Iscritto il: 24/08/2010, 06:50

Re: [Algoritmi] Ricorrenze

Messaggioda FurioShow » 17/11/2018, 15:43

Quinzio ha scritto:Non mi sembra un esercizio banale, l'unica cosa che si vede e' questa:

$T(n) = $

$T(n/2)+ T(n/4) + n$
e adesso scompongo solo $T(n/2)$

$2T(n/4) +T(n/8) + n + n/2$
e qui scompongo solo $T(n/4)$

$3T(n/8) +2T(n/16) + n + n/2 + 2n/4$

$5T(n/16) +3T(n/32) + n + n/2 + 2n/4 + 3n/8$

$Fib(log(n)) + kn $

A sinistra si vede la sequenza di Fibonacci, a destra c'e' qualcosa che non cresce molto rapidamente.
Secondo me oltre a questo risultato non si va.
Come dici tu non vengono date informazioni su cosa fare con termini come $T(k), k<1$, ad es $T(1/2)$.
Si puo' supporre di considerarli tutti uguali a 1.

Scusami avevo sbagliato il testo, il secondo T aveva un 2 che lo moltiplicava, modifico.
FurioShow
New Member
New Member
 
Messaggio: 28 di 60
Iscritto il: 28/09/2017, 15:55

Re: [Algoritmi] Ricorrenze

Messaggioda FurioShow » 17/11/2018, 18:15

Quindi su l'albero di ricorsione non ci sono strade per calcolare il numero di livelli, il generico sottoproblema al livello iesimo e via dicendo?
FurioShow
New Member
New Member
 
Messaggio: 29 di 60
Iscritto il: 28/09/2017, 15:55


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite