admin

Complessità: potenza

di

Pagina 204 del libro di testo T = c1+c2+c3+c4+[…]+c8= c1+c2+c3+c4+[c5+c6+c7]*4+c5+c8= 3*4 + 6= 18 T = c1+c2+c3+c4+c5+c6+[…]+c10= [c7+c8+c9]*n+c7+7= 3*n +1+7= n potenza di 2 T(2) = c1+c2+c3+c4+c5+c6 +[c7+c8+c9+c10] +[c7] +c13+c14 = t2+9 = 13 T(4) = c1+c2+c3+c4+c5+c6 +[c7+c8+c9+c10] +[c7+c8+c9+c10] +[c7] +c13+c14 = 2*t2+9 = 17 T(8) = c1+c2+c3+c4+c5+c6 +[c7+c8+c9+c10] +[c7+c8+c9+c10] +[c7+c8+c9+c10] +[c7] +c13+c14 = 3*t2+9 … Leggi tutto

Complessità: ordinamenti ingenui

di

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

Complessità: la torre di Hanoi

di

Dopo aver analizzato il problema decidiamo che il tempo di esecuzione dell’algoritmo è proporzionale al numero di spostamenti di dischi Numericamente si tratta della successione 1, 3, 7, 15, 31, 63, 127, … cioè 21-1, 22-1, 23-1, 24-1, 25-1, 26-1, 27-1, … quindi T(n) = 2n-1 I tempi necessari per una persona oppure per un … Leggi tutto

Complessità in tempo

di

Considera gli esempi del libro di testo a pagina 198 e successive.La codifica in Python è più leggibile? 1 T(n) = 1+1+1 = 3 Per semplificare i calcoli associamo alle tre istruzioni un costo unitario ma in realtà hanno tempi d’esecuzione molto diversi 2 T(n) = c1 + c2 + c3 + c4 + […] … Leggi tutto