[Algoritmi] Calcolo equazione e costo di ricorsione

[coly40]

Buongiorno a tutti, stavo cercando di risolvere il seguente esercizio di algoritmi e strutture dati sul calcolo di un equazione di ricorrenza. Dal risultato di questa equazione dovrei, successivamente, calcolare la complessità asintotica.

f(i) {
   if(i==0) return 1;
   a = f(i/2) + 2* f(i/2);
   return a - f(i/2) + i;
} 

Potrebbe essere corretta questa equazione di ricorrenza?


$T(N)$ = $\{(1 \to if i = 0),(2* f (i/2) + f (i/2) + 1 \to if i !=0):}$


In caso negativo, quale potrebbe essere? Per calcolare la complessità asintotica posso utilizzare uno dei tre metodi (iterazione, sostituzione o master theorem)?

[vict85]

Prima di tutto, ti farei notare che \(\displaystyle 2f\biggl(\frac{i}{2} \biggr) + f\biggl(\frac{i}{2} \biggr) = 3 f\biggl(\frac{i}{2} \biggr)\). Secondariamente il numero di operazioni non è esattamente \(1\), ma è costante. Quindi scriverei \(O(1)\) invece che \(1\).

A questo punto la ricorsione ha una formula piuttosto standard. Dovresti essere in grado di fare considerazioni sulla sua complessità.

[coly40]

"vict85":Prima di tutto, ti farei notare che \(\displaystyle 2f\biggl(\frac{i}{2} \biggr) + f\biggl(\frac{i}{2} \biggr) = 3 f\biggl(\frac{i}{2} \biggr)\). Secondariamente il numero di operazioni non è esattamente \(1\), ma è costante. Quindi scriverei \(O(1)\) invece che \(1\).

A questo punto la ricorsione ha una formula piuttosto standard. Dovresti essere in grado di fare considerazioni sulla sua complessità.

Ti ringrazio per la risposta, per conferma quindi sarebbe:

$T(N)$ = $\{(O(1) \to if i = 0),(O(nlogn) + O(1) \to if i !=0):}$

[vict85]

Per prima cosa, avresti dovuto scrivere:
\[T(N) = \begin{cases} O(1) & \text{ per } N = 1 \\ 3T(N/2) + O(1) & \text{ per } N > 1 \end{cases}\]
e non usare \(f\). Errore mio che non te l'ho fatto notare prima.

Comunque, come l'hai risolto? Ti suggerisco di riprovare con il master theorem.

[coly40]

"vict85":Per prima cosa, avresti dovuto scrivere:
\[T(N) = \begin{cases} O(1) & \text{ per } N = 1 \\ 3T(N/2) + O(1) & \text{ per } N > 1 \end{cases}\]
e non usare \(f\). Errore mio che non te l'ho fatto notare prima.

Comunque, come l'hai risolto? Ti suggerisco di riprovare con il master theorem.

Si scusami, ho scritto una cavolata nella soluzione precedente.

Con il Master Theorem rientriamo nel primo caso dove: \[c < log_b a \]
ovvero:
\[ 0 < 1,58 \]

quindi:

\[T(N) = \begin{cases} O(1) & \text{ per } N = 1 \\ O(n ^{log_2 3} ) & \text{ per } N > 1 \end{cases}\]

E' corretta questa soluzione? Devo utilizzare O-Grande o Theta?
Grazie