Discussioni su argomenti di Informatica

Regole del forum

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

[Algoritmi] Sommatorie in equazioni di ricorrenza

05/06/2022, 09:32

Data un'equazione di ricorrenza, ho calcolato l'albero di ricorrenza la cui altezza è $h=log_4n$
Il contributo generale al livello i-esimo è $\sqrt(n)$
Adesso, devo calcolare la somma di tutti i contributi usando la formula
$T(n) = \sum_{i=0}^{h}f(x) $
Dove $f(x)$ è il valore del contributo generale. Facendo le giuste sostituzioni mi ritrovo con:
$T(n) = \sum_{i=0}^{log_4n} \sqrt{n} $

Ora, le mie domande sono su come posso gestire la sommatoria e trovare una soluzione per $T(n)$
So che usando la proprietà distributiva posso portare fuori $\sqrt(n)$ in questo modo
$T(n) = \sqrt{n}\sum_{i=0}^{log_4n} 1 $

Mi chiedo:
1- è corretto mettere 1 nell'ultima sommatoria?
2- se sì, è giusto avere poi questa soluzione? $ \sqrt{n} \cdot (log_4n+1)$

Grazie dell'attenzione

Re: [Algoritmi] Sommatorie in equazioni di ricorrenza

05/06/2022, 13:42

sì, puoi farlo.
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.