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]

Originariamente inviato da qwerty86

Si.., esame di fondamenti di programmazione ??

Cosa si fà in questo esame?

[qwerty86]

Originariamente inviato da nico88desmo

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?

[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_]

Originariamente inviato da 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.

Errore di trascrizione, dovrebbe essere:

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

ok?

[71104]

Originariamente inviato da _TeRmInEt_

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
se vedi una cosa del genere in teoria dovresti essere subito in grado di dire O(k)

[_TeRmInEt_]

Originariamente inviato da 71104

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
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

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?

[qwerty86]

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

[nuovoUtente86]

Originariamente inviato da qwerty86

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]

Originariamente inviato da _TeRmInEt_

Questo programma è in Algoritmi e base dati

Quindi i miei calcoli sono giusti?

Milano ?
Se sì, con che docente ?

[_TeRmInEt_]

Originariamente inviato da Nous

Milano ?
Se sì, con che docente ?

Non è Milano

[Nous]

Originariamente inviato da _TeRmInEt_

Non è Milano

Uffi

[_TeRmInEt_]

Per conoscenza, ho preso 27

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

Ciao

[qwerty86]

Originariamente inviato da _TeRmInEt_

Per conoscenza, ho preso 27

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

Ciao

Ottimo , auguri !!!!!