Programmazione

Pagina 210 del libro di testo Calcolare la somma e il prodotto dei numeri naturali da 1 a n 1 T1(n) = = = = 2 T2(n) = = = = Confronto I due algoritmi appartengono alla stessa classe di complessità (lineare) ma… = = < 1 è più efficiente di .

Vedi pagina 206 del libro di testo T(2) = = 5T(3) = = (2)+5 = 7T(4) = = 5T(5) = = 3*(2)+5 = 11T(6) = = 5T(7) = … = 5*(2)+5 = 15… Quindi Il problema di decidere se un numero n è primo affrontato con l’algoritmo delle divisioni successive porta a una complessità in … Leggi tutto

Pagina 204 del libro di testo = = = = 18 T(n) = = = = Calcolare la potenza con l’algoritmo classico porta a una complessità in tempo lineare, , che può essere leggermente migliorata sapendo che n è positivo. Miglioramento Se n è potenza di 2 T(2) = = = 13T(4) = = = … Leggi tutto

Bubble sort Codice analizzato (Pascal) L’istruzione SCAMBIA() viene eseguita ogni volta che ha successo il controllo dell’istruzione If(…) Then.Consideriamo il caso pessimo, cioè che succeda a ogni passo.Quanti sono i controlli e le esecuzioni di SCAMBIA()? i j Numeroconfronti Numeroscambi 1 1…(n-1) n-1 n-1 2 1…(n-2) n-2 n-2 … … … … n-2 1…2 2 2 … Leggi tutto