Passa al tema normale
Discussioni su argomenti di Informatica

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

Equazione di ricorrenza

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à.

Re: Equazione di ricorrenza

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.

Re: Equazione di ricorrenza

09/03/2022, 19:03

Grazie mille lo stesso per il tempo dedicatomi!
Rispondi al messaggio


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.