Complessità: potenza

di

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) = = = = 13 T(4) = … 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.Lo pseudolinguaggio è tradotto in Python. 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) = = = = 3.1 3.2 4 T(n) = = = … Leggi tutto