Calcolo tempo di esecuzione ciclo che varia

[davidinho92]

Dovrei calcolare il tempo di esecuzione T(n) di questa funzione:

funzione(int n)
	c=m=1
	for i=1 to n do
		m=3*m
		for J=1 to m do
			c++
		endfor
	endfor

ora io saprei calcolare il tutto tranquillamente se il ciclo interno si ripetesse per un numero costante di volte, ma sono veramente in difficoltà dato che si va a ripetere per m volte, con m che aumenta ogni volta diventando 3 volte più grande...

qualcuno ha qualche consiglio?

[vict85]

Nel primo ciclo si ripete 1 volta, nella seconda 3, nella terza 9 e così via. Come scriveresti l'i-esimo passaggio?

[davidinho92]

3^i , quindi so che il for interno si ripete per $3^i$ volte, quindi il costo del for interno è $Θ(3^n)$?
per cui la funzione impiega un tempo pari a $Θ(n3^n)$? mi sa che ho sbagliato qualcosa...

[vict85]

Si, ti sei perso un passaggio...

Il numero di operazioni è \(\displaystyle \sum_{i=0}^{n-1} 3^i = \frac{3^n - 1}{3-1} = \frac{3^n - 1}{2} = \Theta(3^n)\)

L'ultimo passaggio è la conosciuta formula per le serie geometriche.

[davidinho92]

ah si, grazie ora ricordo, era molto tempo che non calcolavo il tempo di esecuzione di un algoritmo...
grazie mille

[davidinho92]

scusami pensavo di aver capito ma invece ricontrollando altri algoritmi mi sono reso conto di non aver molto chiaro come hai trovato la soluzione

allora sappiamo che il ciclo for interno ogni volta ha un costo maggiore, aumentando ogni volta di $3^i$, ora questo si ripete per $n$ volte, quindi perché la sommatoria è solo fino a $n-1$ e non fino a $n$?

inoltre una volta "elaborata" la sommatoria fino a
$\sum_{i=0}^{n-1} 3^i = \frac{3^n - 1}{3-1} = \frac{3^n - 1}{2}$
come fai ad ottenere $\Theta(3^n)$ ?

scusami se magari faccio domande stupide ma vorrei cercare di eliminare ogni dubbio...

[vict85]

Arrivo a \(\displaystyle n-1 \) perché al \(\displaystyle i \)-esimo ciclo fa \(\displaystyle 3^{i-1} \) operazioni. Quindi ho semplicemente cambiato l'indice in modo di avere una serie geometrica che partisse da \(\displaystyle 0 \).

Dopo di che ho \(\displaystyle \frac12 3^n - \frac12 = \Theta(3^n) \). Qual'è il problema? Basta selezionare costanti opportune.

[davidinho92]

si, forse ho capito, ti chiedo solo di togliermi un ultimo dubbio, questa funzione mi mette veramente in difficoltà:

f(n)
	i=1
	while(i<n)
		g(i)
		i = 2^i

con $g(n)$ che ha complessità $O(n^(log_3 2))$

inizialmente stavo pensando ad una sommatoria di questo tipo:
$sum_{i=0}^{n-1} O((2^i)^(log_3 2)) + c$

però in realtà non vengono sommati tutti gli elementi in quanto $i$ aumenta in modo esponenziale, quindi qualcosa mi dice che la sommatoria deve avere come limite un logaritmo, però ogni volta si eleva alla $2^i$...

sono veramente confuso...

[jigen45]

Mi scuso se riapro questa discussione, ma mi ritrovo a fare lo stesso identico esercizio e avevo qualche dubbio.

istruzione	costo	n°di volte
$ c_1 $	$ 2 $	for i=1 to n do
$ n $	m=3*m	$ c_3 $
for j=1 to m do	$ c_4 $	$ \sum_{i = 1}^{n} 3^((t_i)) $
$ c_5 $	$ \sum_{i = 1}^{n} 3^((t_i - 1)) $	endfor
$ \sum_{i = 1}^{n} 3^((t_i - 1)) $	endfor	$ 0 $

Sicuramente avrò sbagliato qualcosa, ma avevo visto la notazione delle sommatorie per indicare il numero di volte che un'istruzione veniva eseguita per calcolare il tempo di esecuzione dell'insertion sort (precisamente all'interno del ciclo while). Potete darmi una mano? Grazie