[Algoritmi] calcolo tempo esecuzione funzione mediante ricorrenza (metodo iterativo)
Buonasera ragazzi, volevo calcolare il tempo di esecuzione della seguente funzione mediante metodo iterativo
Allora ho impostato la seguente ricorrenza:
$ T(n)={ ( Theta(an)),( Theta(an) + 2T(n/4)):} $
Il primo rappresenta il caso base ($ n < 2 $), quindi lo ignoro e assumiamo $ Theta(1) $; maggioro $Theta(an)$ con $Theta(n^2)$ dunque la ricorrenza da risolvere è $Theta(n^2)+2T(n/4)$
$ n^2+2T(n/4) = $
a questo punto non so se la ricorrenza diventa
$ =n^2 + 2(n^2/4 +2T(n/16)) $
oppure
$ =n^2 + 2((n/4) +2T(n/16)) $
Inoltre, come faccio a sapere per quanto tempo devo svilupparla? O c'è un modo per evitare lunghi calcoli? Per il resto, ho fatto bene o c'è qualcosa di sbagliato? Grazie in anticipo
fun (intero n) {
i=0;
for a=1 to n do
for b=1 to a do
i++;
if n<2 then return i;
else return 2*fun(n/4);
}Allora ho impostato la seguente ricorrenza:
$ T(n)={ ( Theta(an)),( Theta(an) + 2T(n/4)):} $
Il primo rappresenta il caso base ($ n < 2 $), quindi lo ignoro e assumiamo $ Theta(1) $; maggioro $Theta(an)$ con $Theta(n^2)$ dunque la ricorrenza da risolvere è $Theta(n^2)+2T(n/4)$
$ n^2+2T(n/4) = $
a questo punto non so se la ricorrenza diventa
$ =n^2 + 2(n^2/4 +2T(n/16)) $
oppure
$ =n^2 + 2((n/4) +2T(n/16)) $
Inoltre, come faccio a sapere per quanto tempo devo svilupparla? O c'è un modo per evitare lunghi calcoli? Per il resto, ho fatto bene o c'è qualcosa di sbagliato? Grazie in anticipo
Risposte
"jigen45":
Buonasera ragazzi, volevo calcolare il tempo di esecuzione della seguente funzione mediante metodo iterativo
for a=1 to n do for b=1 to a do i++; }
Allora ho impostato la seguente ricorrenza:
$ T(n)={ ( Theta(an)),( Theta(an) + 2T(n/4)):} $
analizza bene.
Perchè ritieni che il doppio ciclo for sia a costo lineare?
a=1
b=1 to 1
a=2
b=1 to 2
a=3
b=1 to 3
...
a= n
b=1 to n
cioè il secondo ciclo itera da $1$ ad $n$ volte, cioè $1 + 2 + 3 + ... + n = \sum_{b=1}^n b = {n(n+1)}/2$
il primo ciclo è iterato $n$ volte quindi $n*\sum_{b=1}^n b = n*{n(n+1)}/2 = n^3/2+n^2/2$
a te riformalizzare il tutto.
EDIT:
è sbagliato il calcolo, non è da moltiplicare per $n$.
ma infatti ho scritto $ Theta(an) $ non è lineare, però dici tu dovevo scrivere $ Theta(n^2) $ . Mi pare in seguito ho fatto questa considerazione..
"jigen45":
ma infatti ho scritto $ Theta(an) $ non è lineare
Se scrivi così è errato poiché viene considerato lineare.
Perché \(\displaystyle T(n) = \Theta(n^2) + 2T(n/4) \)? A me non sembra che chiami \(\displaystyle T(n/4) \) due volte, ma semplicemente moltiplica tale valore per \(\displaystyle 2 \). Insomma stai solo aggiungendo una operazione, che puoi ignorare.
Quindi hai \(\displaystyle T(n) = \Theta(n^2) + T(n/4) \).
Quindi hai \(\displaystyle T(n) = \Theta(n^2) + T(n/4) \).
"Giova411":
[quote="jigen45"]ma infatti ho scritto $ Theta(an) $ non è lineare
Se scrivi così è errato poiché viene considerato lineare.[/quote]
sì è vero, me ne sono reso conto subito dopo che ti avevo risposto.
"vict85":
Perché \(\displaystyle T(n) = \Theta(n^2) + 2T(n/4) \)? A me non sembra che chiami \(\displaystyle T(n/4) \) due volte, ma semplicemente moltiplica tale valore per \(\displaystyle 2 \). Insomma stai solo aggiungendo una operazione, che puoi ignorare.
Quindi hai \(\displaystyle T(n) = \Theta(n^2) + T(n/4) \).
Insomma quel $ 2 $ non lo considero in quanto costante?
ot: ma quanto ne sai, sei una "spada" anche in teoria dei numeri ed algebra lineare! (le altre sezioni non le ho viste, forse dimentico qualcosa)
mi rimane però il problema iniziale: non so quale delle due ricorrenze è giusta e non so fino a quando devo continuare a sviluppare la ricorrenza..
[ot]
Se contiamo le sole somme e moltiplicazioni (escludendo quelle di supporto per il ciclo) abbiamo \(\displaystyle \sum_{\alpha=1}^n \alpha = \frac{n(n+1)}{2} \) per il ciclo e \(\displaystyle 1 \) moltiplicazione quando \(\displaystyle n\neq \{0, 1\} \). Nota che per via del modo in cui gli interi si dividono dovresti scrivere \(\displaystyle T(n) = \Theta(n^2) + T\bigl(\lfloor n/4 \rfloor\bigr) \) pertanto il comportamento di \(\displaystyle T \) dipenderà dalla scrittura di \(\displaystyle n \) come somma di potenze di \(\displaystyle 4 \). In questo senso la formula generale non è semplicissima. Per semplificare ad una prima analisi puoi soffermarti a \(\displaystyle n = 4^m \).
In questo caso hai che \(\displaystyle T(4^m) = \frac{4^{2m}}{2} + \frac{4^{m}}{2} + 1 + T(4^{m-1}) \). Perciò ha che \(\displaystyle T(4^m) = \frac12\sum_{\alpha=0}^m \bigl(4^2\bigr)^{\alpha} + \frac12\sum_{\alpha=0}^m 4^{\alpha} + m - 2 \) che sono la somma di due progressioni geometriche. Sperando di non aver sbagliato i calcoli. Ricordati poi di riportare il tutto con \(\displaystyle n = 4^m \).
"jigen45":Grazie ma di teoria dei numeri ne so ben poco. Ho fatto corsi in ogni ambito della matematica quindi so qualcosa di tutto. Riguardo all'informatica programmo in modo dilettantistico da più di 10 anni.[/ot]
ot: ma quanto ne sai, sei una "spada" anche in teoria dei numeri ed algebra lineare! (le altre sezioni non le ho viste, forse dimentico qualcosa)
Se contiamo le sole somme e moltiplicazioni (escludendo quelle di supporto per il ciclo) abbiamo \(\displaystyle \sum_{\alpha=1}^n \alpha = \frac{n(n+1)}{2} \) per il ciclo e \(\displaystyle 1 \) moltiplicazione quando \(\displaystyle n\neq \{0, 1\} \). Nota che per via del modo in cui gli interi si dividono dovresti scrivere \(\displaystyle T(n) = \Theta(n^2) + T\bigl(\lfloor n/4 \rfloor\bigr) \) pertanto il comportamento di \(\displaystyle T \) dipenderà dalla scrittura di \(\displaystyle n \) come somma di potenze di \(\displaystyle 4 \). In questo senso la formula generale non è semplicissima. Per semplificare ad una prima analisi puoi soffermarti a \(\displaystyle n = 4^m \).
In questo caso hai che \(\displaystyle T(4^m) = \frac{4^{2m}}{2} + \frac{4^{m}}{2} + 1 + T(4^{m-1}) \). Perciò ha che \(\displaystyle T(4^m) = \frac12\sum_{\alpha=0}^m \bigl(4^2\bigr)^{\alpha} + \frac12\sum_{\alpha=0}^m 4^{\alpha} + m - 2 \) che sono la somma di due progressioni geometriche. Sperando di non aver sbagliato i calcoli. Ricordati poi di riportare il tutto con \(\displaystyle n = 4^m \).
"vict85":Grazie ma di teoria dei numeri ne so ben poco. Ho fatto corsi in ogni ambito della matematica quindi so qualcosa di tutto. Riguardo all'informatica programmo in modo dilettantistico da più di 10 anni.[/ot][/quote]
[ot][quote="jigen45"]ot: ma quanto ne sai, sei una "spada" anche in teoria dei numeri ed algebra lineare! (le altre sezioni non le ho viste, forse dimentico qualcosa)
complimenti
"vict85":
Se contiamo le sole somme e moltiplicazioni (escludendo quelle di supporto per il ciclo) abbiamo \(\displaystyle \sum_{\alpha=1}^n \alpha = \frac{n(n+1)}{2} \) per il ciclo e \(\displaystyle 1 \) moltiplicazione quando \(\displaystyle n\neq \{0, 1\} \). Nota che per via del modo in cui gli interi si dividono dovresti scrivere \(\displaystyle T(n) = \Theta(n^2) + T\bigl(\lfloor n/4 \rfloor\bigr) \) pertanto il comportamento di \(\displaystyle T \) dipenderà dalla scrittura di \(\displaystyle n \) come somma di potenze di \(\displaystyle 4 \). In questo senso la formula generale non è semplicissima. Per semplificare ad una prima analisi puoi soffermarti a \(\displaystyle n = 4^m \).
In questo caso hai che \(\displaystyle T(4^m) = \frac{4^{2m}}{2} + \frac{4^{m}}{2} + 1 + T(4^{m-1}) \). Perciò ha che \(\displaystyle T(4^m) = \frac12\sum_{\alpha=0}^m \bigl(4^2\bigr)^{\alpha} + \frac12\sum_{\alpha=0}^m 4^{\alpha} + m - 2 \) che sono la somma di due progressioni geometriche. Sperando di non aver sbagliato i calcoli. Ricordati poi di riportare il tutto con \(\displaystyle n = 4^m \).
ok grazie mille
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo