Discussioni su argomenti di Informatica
02/03/2022, 17:27
Salve potreste darmi una mano con quest'equazione di ricorrenza?
\(\displaystyle T(n) = \left\{
\begin{array}{ll}
1 & se\ n \le 3 \\
\sqrt[3]{n}*T(\sqrt[3]{n}) + \sqrt[2]{n} & se\ n < 3 \\
\end{array}
\right. \)
Seguendo il metodo iterativo, mi trovo:
$T( root(3)(n))= T(n^(1/3)) = (n^(1/3) * T(n^(1/3)) + n^(1/2))^(1/3) = [n^(1/3)*T(n^(1/3))+n^(1/2)]^(1/3)$
Poi lo sostituisco in $ T(n)$ e mi trovo:
$T(n)= n^(1/3) * [n^(1/3)*T(n^(1/3))+n^(1/2)]^(1/3) +n^(1/2)$
Adesso dovrei fare i calcoli, ma ho difficoltà, potreste spiegarmi i passaggi successivi? Grazie mille a chiunque risponderà.
03/03/2022, 00:18
Ciao @paolobi, benvenuto nel forum.
Non mi sono chiari i passaggi che stai cercando di svolgere. Quello che hai scritto non mi sembra infatti corretto essendo
\[ T(\sqrt[3]{n}) = \sqrt[9]{n}*T(\sqrt[9]{n}) + \sqrt[6]{n} \neq \sqrt[3]{\sqrt[3]{n}*T(\sqrt[3]{n}) + \sqrt[2]{n}}. \]
Come esempio sia \(n = 2^9\). Abbiamo che
\[ 2(1 + \sqrt{2}) \approx 4.82843 \neq \sqrt[3]{2^3\,2(1 + \sqrt{2}) + 2^{9/2}} \approx 3.94197 \]
A prima vista non mi sembra affatto semplice da risolvere.
09/03/2022, 19:03
Grazie mille lo stesso per il tempo dedicatomi!
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.