15/07/2019, 15:34
f(i) {
if(i==0) return 1;
a = f(i/2) + 2* f(i/2);
return a - f(i/2) + i;
}
15/07/2019, 17:55
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à.
16/07/2019, 10:12
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.
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.
Powered by phpBB © phpBB Group - Privacy policy - Cookie privacy
phpBB Mobile / SEO by Artodia.