[Algoritmi] Calcolo equazione e costo di ricorsione

Messaggioda lucaandaloro » 15/07/2019, 15:34

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.

Codice:
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)?
lucaandaloro
Starting Member
Starting Member
 
Messaggio: 2 di 8
Iscritto il: 12/01/2017, 12:49

Re: [Algoritmi] Calcolo equazione e costo di ricorsione

Messaggioda vict85 » 15/07/2019, 17:55

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à.
vict85
Moderatore
Moderatore
 
Messaggio: 9768 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: [Algoritmi] Calcolo equazione e costo di ricorsione

Messaggioda lucaandaloro » 15/07/2019, 19:05

vict85 ha scritto: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):}$
lucaandaloro
Starting Member
Starting Member
 
Messaggio: 3 di 8
Iscritto il: 12/01/2017, 12:49

Re: [Algoritmi] Calcolo equazione e costo di ricorsione

Messaggioda vict85 » 16/07/2019, 10:12

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.
vict85
Moderatore
Moderatore
 
Messaggio: 9769 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: [Algoritmi] Calcolo equazione e costo di ricorsione

Messaggioda lucaandaloro » 16/07/2019, 10:46

vict85 ha scritto: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
lucaandaloro
Starting Member
Starting Member
 
Messaggio: 4 di 8
Iscritto il: 12/01/2017, 12:49


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite