[Java] Eq. ricorrenza di una funzione ricorsiva

[iMax21]

Salve a tutti,
sono alle prese con un esercizio all'apparenza semplice ma che mi ha messo in difficoltà

ho una funzione ricorsiva e ne devo calcolare la complessità, scrivendone l'equazione di ricorrenza:

public static int f(int[] a) { return fric(a, 0, a.length-1); }

static int fric(int[] a, int iniz, int fine) {
if(iniz == fine) return a[iniz];
int med = (iniz+fine)/2;
if(fric(a, iniz, med) > fric(a,med+1, fine)) return fric(a, iniz, med);
else return fric(a, med+1, fine);
} 

ho calcolato la complessità come $T(n) = 3T(n/2)$ più un eventuale tempo costante per le operazioni minori ...e già qui spero di non sbagliarmi!

ora sviluppando questa equazione ottengo:
$T(n/2)=3(3T(n/4))$
$T(n/4)=3(3(3T(n/8)))$
.... eccetera fino a ottenere più in generale:
$T(n)=3^kT(n/2^k))$
ora ho pensato che srotolando ancora e ancora questa equazione ad un certo mi ritroverò con questa parte:
$T(n/2^k)=1$ per cui inevitabilmente $n=2^k$ da cui $k=log n$
perciò:
$T(n)= 3^(log n)* log n$

se fino a qui è tutto giusto (e dubito un pochino ) a quanto corrisponde questa equazione? che complessità ha? $O(2^n)$?

[hamming_burst]

"iMax21":
ho calcolato la complessità come $T(n) = 3T(n/2)$ più un eventuale tempo costante per le operazioni minori ...e già qui spero di non sbagliarmi!

ad una rapida occhiata direi ok.

$T(n) = 3T(n/2) + c$

Nello sviluppo dell'equazione ti dimentichi delle costanti.

"iMax21":ora sviluppando questa equazione ottengo:
$T(n/2)=3(3T(n/4))$
$T(n/4)=3(3(3T(n/8)))$

più formalmente dovresti anche sostituire la costante:
$T(n)=3T(n/2) +c $
$T(n/2)=3(3T(n/4) + c) + c$
...

"iMax21":$T(n)= 3^(log n)* log n$

da dove salta fuori quel $* log n$?

la base del logaritmo è $2$ perchè la ricorrenza si ferma quando $n/2^k = 1$ cioè quando $k=log_2(n)$ è importante scriverlo.

"iMax21":se fino a qui è tutto giusto (e dubito un pochino ) a quanto corrisponde questa equazione? che complessità ha? $O(2^n)$?

ti ricordo la proprietà:

$a^{\log_b(n)} = n^{\log_b(a)}$

[iMax21]

innanzitutto ti ringrazio molto per la risposta

ho riguardato il tutto e più correttamente direi che mi ritrovo dopo aver visto che $ k = log n $ (con logaritmo in base 2) posso riscrivere il tutto come:

$T(n)=3^logn T(n/logn)$

ma continuo a non saper come sviluppare il tutto..

[hamming_burst]

"iMax21":
$T(n)=3^logn T(n/logn)$

da dove esce questa sostituzione... (ricorda da inserire la costante!! è importante)
Ma era ben corretto il tuo procedimento.
Infatti a T(1) trovi:

$sum_{k=0}^{\log_2(n)} 3^k \approx 3^{\log_2(n)} = n^{\log_2(3)}$

Una fonferma la trovi anche con il Master:

$3T(n/2) + c$
$a=3$
$b=2$

$c \in O(1)$
$O(1$) si puà esprimere come $n^0$

$n^0 \in O(n^{\log_2(3)-\epsilon})$
a maniche molto larghe con $\epsilon=1$ possiamo dire che $T(n) \in \Theta(n^1.59)$

[iMax21]

Chiedo venia, oggi non è proprio giornata,

Sto riprovando con calma con il teorema master con il quale mi trovo sempre bene,
Le dimostrazioni per passaggi invece non riesco ad arrivare mai a conclusione...cioè una volta individuata l'equazione di ricorrenza, come faccio a trovarne la complessità?

L'unico metodo che ho appreso è "srotolare" l'equazione dalla quale solitamente si trova una equivalenza come per questo caso con $k=logn$ e utilizzarla per semplificare l'equazione stessa, ma non riesco mai a venirne fuori matematicamente, intuitivamente riesco a comprendere la complessità ma dimostrarla è sempre una tragedia

[hamming_burst]

"iMax21":Sto riprovando con calma con il teorema master con il quale mi trovo sempre bene,

sul Master bisogna stare attenti nei casi degeneri come questo. Io ho utilizzato un $\epsilon$ ai limiti, anche se lo ho visto utilizzare più lasco, una limitazione di esso accettabile è $0 < \epsilon <= 1$. Se scelto a caso tipo $2$ si arriva in assurdi, come salti di grandezze polinomiali. Ma va bene utilizzarlo per farsi un'idea di che complessità si tratti "ad occhio".

Su questo ti consiglio di dare una letta a questi post:
- viewtopic.php?f=15&t=104061
- viewtopic.php?f=15&t=106903
- viewtopic.php?p=599886
e più interessante con confronti di più tecniche:
- viewtopic.php?p=595334#p595334

"iMax21":Le dimostrazioni per passaggi invece non riesco ad arrivare mai a conclusione...cioè una volta individuata l'equazione di ricorrenza, come faccio a trovarne la complessità?

dimostrazioni di tipo induttivo, oppure delle ricorrenze?

"iMax21":L'unico metodo che ho appreso è "srotolare" l'equazione dalla quale solitamente si trova una equivalenza come per questo caso con $k=logn$ e utilizzarla per semplificare l'equazione stessa, ma non riesco mai a venirne fuori matematicamente, intuitivamente riesco a comprendere la complessità ma dimostrarla è sempre una tragedia

ci sono almento cinque metodi:

- iterazione
- sostituzione di variabili
- sotituzione (induzione...)
- albero
- master

poi ce ne sono più specializzati come il telescoping, o più "matematici".
Quello più intuitivo e "grafico" è l'albero, almeno io lo trovo piuttosto comodo, anche se comporta un po' di conti. Ma sta difatto che per risolvere tali equazioni bisogna avere un po' di manegevolezza con logaritmi, sommatorie, potenze, ..., cose basilari che si apprendono facendo un po' di esercizio.

Se hai difficoltà in tutto questo, in questa sezione ne abbiamo risolte a centinaia. prova a fare una ricerca con "ricorrenze"... se trovi difficoltà posta pure qualche esercizio con i dubbi e dove ti sei bloccato.

[iMax21]

ti ringrazio ancora per l'aiuto, mi documento meglio e vado a cercare un po' di ricorrenze già trattate grazie!