Calcolo della complessità di un algoritmo

[_TeRmInEt_]

while(k>=0)
{
y=y*x+coef[k];
k--;
}


Vi chiederei una conferma, sono arrivato a questi risultati:

Caso Ottimo

(k=0) -> T(n)= 1+1=2=O(1)

Caso pessimo

(k>0) -> T(n)= 1+n(1+1+1)+1 = 3n+2 = O(n)

Grazie :)

[qwerty86]

Si.., esame di fondamenti di programmazione ??

[nico88desmo]

Si.., esame di fondamenti di programmazione ??

Cosa si fà in questo esame?

[qwerty86]

Cosa si fà in questo esame?

Complessità degli algoritmi , automi , alcuni algoritmi fondamentali ( ordinamento , ricerca) e altre cose che ora non ricordo .

[_TeRmInEt_]

Questo programma è in Algoritmi e base dati :)

Quindi i miei calcoli sono giusti? :cool:

[71104]

scusa ma perché O(n)? dove lo vedi n? io direi che quell'algoritmo è O(k) per il semplice motivo che itera finché k non scende a 0 e decrementa k ad ogni iterazione.

[_TeRmInEt_]

scusa ma perché O(n)? dove lo vedi n? io direi che quell'algoritmo è O(k) per il semplice motivo che itera finché k non scende a 0 e decrementa k ad ogni iterazione.

Errore di trascrizione, dovrebbe essere:

(k>0) -> T(n)= 1+k(1+1+1)+1 = 3k+2 = O(k)

ok?

[71104]

Errore di trascrizione, dovrebbe essere:

(k>0) -> T(n)= 1+k(1+1+1)+1 = 3k+2 = O(k)

ok? si ma non capisco perché spremersi con le equazioni ricorsive quando si vede subito che è un algoritmo di complessità lineare: c'è una sola iterazione ed è basata su un contatore che scende linearmente, c'è poco da fare :D
se vedi una cosa del genere in teoria dovresti essere subito in grado di dire O(k)

[_TeRmInEt_]

si ma non capisco perché spremersi con le equazioni ricorsive quando si vede subito che è un algoritmo di complessità lineare: c'è una sola iterazione ed è basata su un contatore che scende linearmente, c'è poco da fare :D
se vedi una cosa del genere in teoria dovresti essere subito in grado di dire O(k)

Si quello si, che la complessità fosse lineare si capisce benissimo dalla decomposizione del polinomio secondo Horner... ma i prof. sono amanti di formalismi :D

Quindi l'algoritmo è ottimo quando il polinomio è di primo grado:

(k=0) -> T(n)= 1+1=2=O(1)

Pessimo con grado ennesimo:

(k>0) -> T(n)= 1+k(1+1+1)+1 = 3k+2 = O(k)

Giusto? :D

[qwerty86]

Si in genere se c'è un ciclio , che cicla n volte la complessità è data da n * la complessità presente nel ciclo .

[nuovoUtente86]

Si in genere se c'è un ciclio , che cicla n volte la complessità è data da n * la complessità presente nel ciclo .

esatto.essendo tutte le operazioni interne al ciclo costanti o di costo unitario la complessità è pari al ciclo esterno ovvero lineare.

[_TeRmInEt_]

Grazie ;)

[Nous]

Questo programma è in Algoritmi e base dati :)

Quindi i miei calcoli sono giusti? :cool:

Milano ?
Se sì, con che docente :asd:?

[_TeRmInEt_]

Milano ?
Se sì, con che docente :asd:?

Non è Milano :)

[Nous]

Non è Milano :)

Uffi :O

[_TeRmInEt_]

Per conoscenza, ho preso 27

I 3 punti sono dipese da due errorini in fase di stesura della relazione :cry:

Ciao

[qwerty86]

Per conoscenza, ho preso 27

I 3 punti sono dipese da due errorini in fase di stesura della relazione :cry:

Ciao

Ottimo , auguri !!!!! :cincin: