Dimostrazione calcolo complessità

Slashino1
Salve a tutti, qualcuno potrebbe spiegarmi come si arriva a dire che la somma di un numero di parti di codice ciascuno con complessita $ \theta(1) $ ci da una complessità complessiva pari a $ \theta(1) $, mentre se il numero delle parti di codice è dipende da $n$ otteniamo $\theta(n) $?
In parole povere: perchè $4\theta(1)= \theta(1)$ mentre $n\theta(1)=\theta(n) $?

Risposte
hamming_burst
$4\theta(1)$ vuol dire che ci son 4 operazioni a tempo costante. Perciò nel complessot ha complessità $\theta(1)$. Ovviamente puoi scrivere anche $\theta(4)$ non cambia (ricorda che c'è una costante nascosta dietro la notazione $O(1) -> c*1$), è solo una convenzione per dire che sono operazioni costanti (utilizzare altre numerazioni ha senso in altri ambiti dove si deve essere più precisi).

$n\theta(1)$ vuol dire che si son $n$ operazioni a tempo costante, perciò di conseguenza la complessità sarà funzione di $n$.

Slashino1
Ok ti ringrazio, pensavo ci fosse qualcosa di più elaborato dietro :D

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.