1
Ricorsione(capitolo 12)
2
Il calcolo del fattorialeLa funzione fattoriale, molto usata nel calcolo
combinatorio, è così definita
dove n è un numero intero non negativo
0 se 0 se
)!1(1
!>=
−=
nn
nnn
3
Il calcolo del fattorialeVediamo di capire cosa significa…
0! = 1 1! = 1(11)! = 1∙0! = 1∙1 = 1 2! = 2(21)! = 2∙1! = 2∙1 = 2 3! = 3(31)! = 3∙2! = 3∙2∙1 = 6 4! = 4(41)! = 4∙3! = 4∙3∙2∙1 = 24 5! = 5(51)! = 5∙4! = 5∙4∙3∙2∙1 = 120
Quindi, per ogni n intero positivo, il fattoriale di n è il prodotto dei primi n numeri interi positivi
4
Il calcolo del fattorialeScriviamo un metodo statico per calcolare il fattoriale
public static int factorial(int n){ if (n < 0) throw new IllegalArgumentException();
if (n == 0) return 1;
int p = 1; for (int i = 2; i <= n; i++) p = p * i; return p;}
5
Il calcolo del fattorialeFin qui, nulla di nuovo… però abbiamo dovuto fare
un’analisi matematica della definizione per scrivere l’algoritmo
Realizzando direttamente la definizione, sarebbe stato più naturale scrivere
public static int factorial(int n){ if (n < 0) throw new IllegalArgumentException(); else if (n == 0) return 1; else return n * factorial(n - 1);}
6
Il calcolo del fattoriale
Si potrebbe pensare: “Non è possibile invocare un metodo mentre si esegue il metodo stesso!”
Invece, come è facile verificare scrivendo un programma che usi factorial, questo è lecito in Java così come è lecito in quasi tutti i linguaggi di
programmazione
public static int factorial(int n){ if (n < 0) throw new IllegalArgumentException(); else if (n == 0) return 1; else return n * factorial(n - 1);}
7
Invocazione di un metodo ricorsivo
8
Invocare un metodo ricorsivo Invocare un metodo mentre si esegue lo stesso
metodo è un paradigma di programmazione che si chiama ricorsione
e un metodo che ne faccia uso si chiama metodo ricorsivo
La ricorsione è uno strumento molto potente per realizzare alcuni algoritmi, ma è anche fonte di molti errori di difficile diagnosi
9
Invocare un metodo ricorsivoPer capire come utilizzare correttamente la
ricorsione, vediamo innanzitutto come funzionaQuando un metodo ricorsivo invoca se stesso, la
macchina virtuale Java esegue le stesse azioni che vengono eseguite quando viene invocato un metodo qualsiasi sospende l’esecuzione del metodo invocante esegue il metodo invocato fino alla sua terminazione riprende l’esecuzione del metodo invocante dal
punto in cui era stata sospesa
10
Invocare un metodo ricorsivo Invochiamo factorial(3) per calcolare 3!
factorial(3) invoca factorial(2)• factorial(2) invoca factorial(1)
– factorial(1) invoca factorial(0)» factorial(0) restituisce 1
– factorial(1) restituisce 1• factorial(2) restituisce 2
factorial(3) restituisce 6Si crea quindi una pila di metodi “in attesa”, che si
allunga e che poi si accorcia fino ad estinguersipublic static int factorial(int n){ if (n < 0) throw new IllegalArgumentException(); else if (n == 0) return 1; else return n * factorial(n - 1); }
11
La ricorsione: caso basePrima regola
il metodo ricorsivo deve fornire la soluzione del problema in almeno un caso particolare, senza ricorrere ad una chiamata ricorsiva
tale caso si chiama caso base della ricorsione nel nostro esempio, il caso base è
a volte ci sono più casi base, non è necessario che sia unico
if (n == 0) return 1;
12
La ricorsione: passo ricorsivoSeconda regola
il metodo ricorsivo deve effettuare la chiamata ricorsiva dopo aver semplificato il problema
nel nostro esempio, per il calcolo del fattoriale di n si invoca la funzione ricorsivamente per conoscere il fattoriale di n1, cioè per risolvere un problema più semplice
il concetto di “problema più semplice” varia di volta in volta: in generale, bisogna avvicinarsi ad un caso base
if (n > 0) return n * factorial(n - 1);
13
La ricorsione: un algoritmo?Queste due regole sono fondamentali per dimostrare
che la soluzione ricorsiva di un problema sia un algoritmo in particolare, che termini in un numero finito di passi
Si potrebbe pensare che le chiamate ricorsive si susseguano una dopo l’altra, all’infinito. Invece se Ad ogni invocazione il problema diventa sempre più
semplice e si avvicina al caso base E la soluzione del caso base non richiede ricorsione
allora certamente la soluzione viene calcolata in un numero finito di passi, per quanto complesso possa essere il problema
14
Ricorsione infinitaQuanto detto ci suggerisce che non tutti i metodi
ricorsivi realizzano algoritmi se manca il caso base, il metodo ricorsivo continua ad
invocare se stesso all’infinito se il problema non viene semplificato ad ogni
invocazione ricorsiva, il metodo ricorsivo continua ad invocare se stesso all’infinito
Dato che la lista dei metodi “in attesa” si allunga indefinitamente l’ambiente runtime esaurisce la memoria disponibile
per tenere traccia di questa lista ed il programma termina con un errore
15
Ricorsione infinitaUn programma che presenta ricorsione infinita:
Il programma terminerà con la segnalazione dell’eccezione StackOverflowError il runtime stack è la struttura dati all’interno
dell’interprete Java che gestisce le invocazioni in attesa stack significa pila
public class InfiniteRecursion{ public static void main(String[] args) { main(args); }}
16
Eliminare la ricorsione
17
La ricorsione in codaEsistono diversi tipi di ricorsione Il modo visto fino ad ora si chiama ricorsione in
coda (tail recursion) il metodo ricorsivo esegue una sola invocazione
ricorsiva e tale invocazione è l’ultima azione del metodo
public void tail(...){ ... tail(...);}
18
Eliminare la ricorsione in codaLa ricorsione in coda può sempre essere
agevolmente eliminata, trasformando il metodo ricorsivo in un metodo che usa un ciclo
public int factorial(int n){ if (n == 0) return 1; else return n * factorial(n - 1);}
public int factorial(int n){ int f = 1; while (n > 0) { f = f * n; n--; } return f;}
19
Eliminare la ricorsione in codaAllora, a cosa serve la ricorsione in coda?Non è necessaria, però in alcuni casi rende il codice
più leggibileÈ utile quando la soluzione del problema è
esplicitamente ricorsiva (ad esempio nel calcolo della funzione fattoriale)
In ogni caso, la ricorsione in coda è meno efficiente del ciclo equivalente, perché il sistema deve gestire le invocazioni sospese
20
Eliminare la ricorsioneSe la ricorsione non è in coda, non è facile eliminarla
(cioè scrivere codice non ricorsivo equivalente), però si può dimostrare che ciò è sempre possibile deve essere così, perché il processore esegue
istruzioni in sequenza e non può tenere istruzioni in attesa
In Java l’interprete si fa carico di eliminare la ricorsione (usando il runtime stack)
In un linguaggio compilato il compilatore trasforma il codice ricorsivo in codice macchina non ricorsivo
21
Ricorsione multipla e problemi di efficienza
22
La ricorsione multiplaSi parla di ricorsione multipla quando un metodo
invoca se stesso più volte durante la propria esecuzione la ricorsione multipla è ancora più difficile da eliminare,
ma è sempre possibileEsempio: il calcolo dei numeri di Fibonacci
3 se 31 se
)1Fib()2Fib(1
)Fib(≥
<≤
−+−=
nn
nnn
23
La classe FibTesterpublic class FibTester{ private static int invcount = 0; // variabile statica public static void main(String[] args) { int n = 0; if (args.length != 1) { System.out.println("Uso: $java FibTester <numero>"); System.exit(1); } try { n = Integer.parseInt(args[0]); } catch(NumberFormatException e) { System.out.println("Inserire un intero!"); System.exit(1); } System.out.println("*** Collaudo iterativeFib ***"); for (int i = 1; i <= n; i++) { long f = iterativeFib(i); System.out.println("iterativeFib(" +i+ ") = " + f);} System.out.println("\n*** Collaudo recursiveFib ***"); for (int i = 1; i <= n; i++) { invcount = 0; long f = recursiveFib(i); System.out.println("recursiveFib(" +i+ ") = " + f); System.out.println(invcount+" invocazioni"); } } //continua 24
La classe FibTester public static long recursiveFib(int n) //continua { if (n < 1) throw new IllegalArgumentException(); System.out.println("Inizio recursiveFib(" + n +")"); invcount++; long f; if (n < 3) f = 1; else f = recursiveFib(n-1) + recursiveFib(n-2); System.out.println("Uscita recursiveFib(" + n + ")"); return f; } public static long iterativeFib(int n) { if (n < 1) throw new IllegalArgumentException(); long f = 1; if (n >= 3) { long fib1 = 1; long fib2 = 1;
for (int i = 3; i<=n; i++) { f = fib1 + fib2; fib2 = fib1; fib1 = f; }
} return f; }}
25
La ricorsione multipla Il metodo fib realizza una ricorsione multiplaLa ricorsione multipla va usata con molta attenzione,
perché può portare a programmi molto inefficientiEseguendo il calcolo dei numeri di Fibonacci di
ordine crescente Si nota che il tempo di elaborazione cresce molto
rapidamente Sono necessarie quasi 3 milioni di invocazioni per
calcolare Fib(31) !!!! più avanti quantificheremo questo problema
Invece una soluzione iterativa risulta molto più efficiente
26
Albero delle invocazioni di fibVisualizziamo lo schema delle invocazioni di fib in
una struttura ad alberoLo stesso valore viene calcolato più volte
Molto inefficiente
27
Permutazioni(cfr. sezione 12.2)
28
Esaminiamo un problema per il quale è (relativamente) facile trovare una soluzione ricorsiva mentre è molto difficile trovarne una iterativa
Problema: determinare tutte le possibili permutazioni dei caratteri presenti in una stringa facciamo l’ipotesi che non ci siano caratteri ripetuti
Ricordiamo dalla matematica combinatoria che il numero di permutazioni di N simboli è N!
Esempio: ABC ABC ACB BAC BCA CAB CBA
Permutazioni
29
La classe PermutationTester
Dobbiamo trovare una buona idea per scrivere il metodo getPermutations…
import java.util.Scanner;public class PermutationTester{ public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.println("Inserire stringa"); String aString = in.nextLine(); String[] permutations = getPermutations(aString); for (int i = 0; i < permutations.length; i++) System.out.println(permutations[i]); }
public static String[] getPermutations(String word) {...}
30
Esiste un semplice algoritmo ricorsivo per trovare le permutazioni di una stringa di lunghezza N
Se N vale 1, l’unica permutazione è la stringa stessaAltrimenti
Generiamo tutte le permutazioni che iniziano con il primo carattere
Generiamo tutte le permutazioni che iniziano con il secondo carattere
… e così via Otteniamo tutte le possibili permutazioni Esempio: ABC ACB BAC BCA CAB CBA
Permutazioni
31
PermutazioniCome si ottengono le permutazioni che iniziano con il
generico iesimo carattere? Concatenando l’iesimo carattere con tutte le
permutazioni della stringa composta dai rimanenti N1 caratteri
Cioè risolvendo lo stesso problema per un dato di dimensione più piccola
Esempio: ABC ACB BAC BCA CAB CBAAbbiamo ottenuto il passo di ricorsione!Avevamo già il caso base
Se N = 1 c’è una sola permutazione, la stringa stessa Il passo di ricorsione semplifica il problema e si
avvicina al caso base32
Il metodo getPermutationspublic static String[] getPermutations(String word){ if (word == null || word.length() == 0) //precondizioni return new String[0]; // oppure return null
if (word.length() == 1) // caso base return new String[] {word};
int nperm = 1; // il n. di permutazioni da generare... for (int i = 2; i <= word.length(); i++) nperm *= i; // ... e` il fattoriale di word.length() String[] perm = new String[nperm];
for (int i = 0; i < word.length(); i++) { String subword = word.substring(0,i)+ word.substring(i+1); // passo ricorsivo: permutazioni della sottosequenza String[] subperm = getPermutations(subword); for (int j = 0; j < subperm.length; j++) perm[i*subperm.length+j] = word.substring(i,i+1) + subperm[j]; } return perm;}
33
PermutazioniCommenti sulla gestione delle precondizioni
Il metodo riceve un riferimento ad una stringa: tale riferimento può essere null oppure la stringa può essere vuota (cioè avere lunghezza zero)
In alternativa al lancio di una eccezione si può restituire null, o nel caso di un array è lecito restituire un array di lunghezza zero in modo che il metodo invocante riceva un array valido
In questo modo, il codice seguente funziona…
mentre non funzionerebbe se restituissimo null
//ATTENZIONE: stiamo sfruttando la//valutazione pigra dell'operatore ORif (word == null || word.length() == 0) return new String[0];
String[] permutations = getPermutations(“”); for (int i = 0; i<permutations.length; i++) System.out.println(permutations[i]);
34
Permutazioni
Quando creiamo l’array che dovrà contenere le permutazioni dobbiamo definirne la dimensione
La dimensione del vettore che conterrà le permutazioni può essere calcolata sfruttando la nostra conoscenza del problema Sappiamo che le permutazioni sono N!
// numero di permutazioni da generare int nperm = 1; for (int i = 2; i <= word.length(); i++) nperm *= i; String[] perm = new String[nperm];
35
Permutazioni
In alternativa potremmo sfruttare le informazioni ottenute dall’invocazione ricorsiva Il numero di permutazioni è uguale a
• la dimensione della stringa • moltiplicata per il numero di permutazioni generate da una
sottosequenza di lunghezza N1 Dovremmo effettuare la prima invocazione ricorsiva fuori
dal ciclo.
// numero di permutazioni da generare: String subword = word.substring(0,0) + word.substring(1);String[] subperm = getPermutations(subword);String[] perm = new String[word.length() * subperm.length];for (int j = 0; j < subperm.length; j++) { perm[j] = word.substring(0,1) + subperm[j]; }
36
Permutazioni
Per completare le permutazioni: concateniamo l’iesimo carattere con tutte le posizioni
permutazioni della corrispondente sottosequenza Aggiungiamo nell’array le permutazioni ottenute
for (int i = 0; i < word.length(); i++){ // eliminiamo l'i-esimo carattere subword = word.substring(0,i) + word.substring(i+1); // passo ricorsivo: permutazioni della sottosequenza subperm = getPermutations(subword); for (int j = 0; j < subperm.length; j++) { perm[i*subperm.length+j] = word.substring(i,i+1) + subperm[j]; }}
37
Per ottenere subword stiamo sfruttando le proprietà del metodo substring
Quando i vale 0, substring restituisce una stringa vuota, che è proprio ciò che vogliamo
Quando i vale word.length( )1 (suo valore massimo), allora i+1 vale word.length( ) in questo caso particolare, substring non lancia
eccezione, ma restituisce una stringa vuota, che è proprio ciò che vogliamo
Permutazioni
word.substring(0,i) + word.substring(i+1);
word.substring(0,i) + word.substring(i+1);
38
Analizziamo meglio questa espressione dell’indiceGlobalmente, tale indice deve andare da 0 a
(word.length())! (escluso)Verifichiamo innanzitutto i limiti
per i = 0 e j = 0, l’indice vale 0 Per un generico i e j = subperm.length1 l’indice vale
i*subperm.length +subperm.length1 = (i+1)*subperm.length 1
Per i =word.length()1, j =subperm.length1, l’indice vale
word.length()*subword.length 1
Permutazioniperm[i*subperm.length+j] = ...;
39
Alla prima iterazione di i, l’indice varia tra 0 e subword.length1 (perché i vale 0)
Alla seconda iterazione di i, l’indice varia tra 1*subword.length+0 = subword.length1*subword.length+shorterword.length1 =
2*subword.length1Si osserva quindi che gli indici vengono generati
consecutivamente, senza nessun valore mancante e senza nessun valore ripetuto
Permutazioniperm[i*subperm.length+j] = ...;
40
Esercizio: torri di Hanoi(cfr. esercizio P12.13)
41
Torri di HanoiScopo del gioco:
Spostare la torre di dischi da un piolo “origine” ad un piolo “destinazione”
Regole del gioco: Si può spostare un solo disco per volta In ogni istante un disco non può poggiare su un
disco più piccolo
42
Torri di Hanoi: soluzione ricorsivaCerchiamo una soluzione ricorsivaDobbiamo trovare
un caso base Un passo di ricorsione che semplifica il problema
Il caso base è semplice: Se la torre è composta da un solo disco la soluzione
è composta da una sola mossa, che sposta il disco stesso dal piolo di origine al piolo di destinazione
43
Torri di Hanoi: soluzione ricorsivaCerchiamo il passo ricorsivo
Ad un certo punto del gioco il disco più grande verrà spostato dall’origine alla destinazione
In quel momento tutti gli altri dischi devono essere impilati sul piolo rimanente
• Ovvero in quel momento abbiamo risolto il problema con n1 dischi
Dopo avere spostato il disco più grande dall’origine alla destinazione, dobbiamo spostare tutti gli altri dischi dal piolo rimanente alla destinazione
• Ovvero dobbiamo nuovamente risolvere il problema con n1 dischi
44
Torri di HanoiRealizziamo una classe DiskMover, il cui costruttore
riceve: il piolo sorgente from da cui prelevare i dischi (1, 2, 3) il piolo destinazione target in cui inserire i dischi (1, 2, 3) il numero di dischi da spostare, disks
Se disks = 1, il DiskMover ha un metodo nextMove che restituisce la mossa da effettuare
Un DiskMover che deve spostare più dischi deve faticare di più, e ha bisogno di un altro oggetto di tipo DiskMover che lo aiuti. Nel costruttore, costruiremo un oggetto in questo modo:
DiskMover(from, other, disks – 1), dove other è il piolo diverso da from e da target.
45
Prima soluzione: la classe HanoiSolverScriviamo un metodo statico ricorsivo solveHanoi
public class HanoiSolver{ public static void main(String[] args) { if (args.length != 3) { System.out.println("uso: $java HanoiSolver from target disks"); System.out.println("con from e target tra 1 e 3, e disks > 0"); return; }
try { solveHanoi(Integer.parseInt(args[0]), Integer.parseInt(args[1]), Integer.parseInt(args[2])); } catch(NumberFormatException e) { System.out.println("Non hai inserito parametri di tipo int"); } catch(IllegalArgumentException e) { System.out.println("Valore errato per from o target o disks"); } } // continua
46
// continua
public static void solveHanoi(int from, int target, int disks) { if (from==target || from<1 || from>3 || target<1 || target>3 || disks<0) throw new IllegalArgumentException();
if (disks > 0) { int other = 6 - from - target; solveHanoi(from, other, disks-1);
System.out.println("Sposta un disco dal piolo " + from + " al piolo " + target); solveHanoi(other, target, disks-1); } }}
Prima soluzione: la classe HanoiSolver
47
ApprofondimentoSeconda soluzione: le classi
Diskmover e HanoiTester(soluzione dell'esercizio P12.13)
48
La classe DiskMoverpublic class DiskMover{ public DiskMover(int from, int target, int disks) { if (from == target || from <1 || from > 3 || target < 1
|| target > 3 || disks < 1) throw new IllegalArgumentException(); this.from = from; this.target = target; this.disks = disks; state = BEFORE_LARGEST; int other = 6 - from - target; if (disks > 1) mover = new DiskMover(from, other, disks - 1); } public boolean hasMoreMoves() { return state != DONE; } // continua
49
La classe DiskMoverpublic int[] nextMove() // continua{ if (!hasMoreMoves()) throw new IllegalStateException(); if (disks == 1) //caso base { state = DONE; return new int[] {from, target}; } if (state == LARGEST) //1o sottoproblema risolto: ora { //si sposta il disco maggiore e si state = AFTER_LARGEST;//imposta il 2o sottoproblema int other = 6 - from - target; mover = new DiskMover(other, target, disks -1); return new int[] {from, target}; } int[] r = mover.nextMove(); //passo ricorsivo if (!mover.hasMoreMoves()) //se mover non ha piu` mosse, { //questo significa che if (state ==BEFORE_LARGEST)//o il 1o sottopr. e` risolto state = LARGEST; else //oppure il gioco e` finito state = DONE; } return r;} // continua 50
La classe DiskMover // continua //campi di esemplare private int from; private int target; private int disks; private DiskMover mover; private int state; //variabili (costanti) di classe private static final int BEFORE_LARGEST = 1; private static final int LARGEST = 2; private static final int AFTER_LARGEST = 3; private static final int DONE = 4;}
51
La classe HanoiTesterpublic class HanoiTester{ public static void main(String[] args) { DiskMover mover = null; try{
int from = Integer.parseInt(args[0]);int target = Integer.parseInt(args[1]);int disks = Integer.parseInt(args[2]);mover = new DiskMover(from, target, disks);while(mover.hasMoreMoves()) { int[] move = mover.nextMove(); System.out.println("Sposta un disco dal piolo "
+ move[0] + " al piolo " + move[1]); }
} catch(NumberFormatException e){ System.out.println(e);} catch(IllegalArgumentException e){ System.out.println(e);} catch(ArrayIndexOutOfBoundsException e) {System.out.println(e);} }}
52
53
Ordinamento e ricerca[e analisi delle prestazioni]
(capitolo 13)
54
MotivazioniProblema molto frequente nella elaborazione dei dati
Ordinamento dei dati stessi, secondo un criterio prestabilito
Ad esempio: nomi in ordine alfabetico, numeri in ordine crescente…
Studieremo diversi algoritmi per l’ordinamento, introducendo anche uno strumento analitico per la valutazione delle loro prestazioni
Su dati ordinati è poi possibile fare ricerche in modo molto efficiente, e studieremo algoritmi adeguati
Studieremo degli algoritmi ricorsivi ed efficienti, ma non tutti gli algoritmi ricorsivi sono efficienti...
55
Ordinamento per selezione
56
Ordinamento per selezionePer semplicità, analizzeremo prima gli algoritmi per
ordinare un insieme di numeri (interi) memorizzato in un array vedremo poi come si estendono semplicemente al caso
in cui si debbano elaborare oggetti anziché numeriPrendiamo in esame un array a da ordinare in senso
crescente
11 9 17 5 12a[0] a[1] a[2] a[3] a[4]
5 9 11 12 17a[0] a[1] a[2] a[3] a[4]
57
5Ordinamento per selezione
Per prima cosa, bisogna trovare l’elemento dell’array contenente il valore minimo, come sappiamo già fare in questo caso è il numero 5 in posizione a[3]
Essendo l’elemento minore, la sua posizione corretta nell’array ordinato è a[0] in a[0] è memorizzato il numero 11, da spostare non sappiamo quale sia la posizione corretta di 11
• lo spostiamo temporaneamente in a[3] quindi, scambiamo a[3] con a[0]
11 9 17 12a[0] a[1] a[2] a[3] a[4]
5 9 17 11 12
58
Ordinamento per selezione
La parte sinistra dell’array è già ordinata e non sarà più considerata Dobbiamo ancora ordinare la parte destra
Ordiniamo la parte destra con lo stesso algoritmo cerchiamo l’elemento contenente il valore minimo, che
è il numero 9 in posizione a[1] dato che è già nella prima posizione a[1] della parte
da ordinare, non c’è bisogno di fare scambi
5 9 17 11 12a[0] a[1] a[2] a[3] a[4]
la parte colorata dell’array è già ordinata
5 9 17 11 12a[0] a[1] a[2] a[3] a[4]
59
11
Ordinamento per selezione
Proseguiamo per ordinare la parte di array che contiene gli elementi a[2], a[3] e a[4] il valore minimo è il numero 11, contenuto
nell’elemento a[3] scambiamo a[3] con a[2]
5 9 17 12a[0] a[1] a[2] a[3] a[4]
5 9 11 17 12 175 9 11 12a[0] a[1] a[2] a[3] a[4]
60
17
Ordinamento per selezione
Ora l’array da ordinare contiene a[3] e a[4] Il valore minimo è il numero 12, contenuto
nell’elemento a[4] scambiamo a[4] con a[3]
A questo punto la parte da ordinare contiene un solo elemento, quindi è ovviamente ordinata
5 9 11 12a[0] a[1] a[2] a[3] a[4]
5 9 11 12 17 125 9 11 17a[0] a[1] a[2] a[3] a[4]
61
Ordinamento per selezione= accesso in lettura = accesso in scrittura
12
11
17
911 17 5 12 5 9 17 11 12
95 11 12 5 9 17 11 12
1795 12 5 9 11 17 12
171195 5 9 11 12 17
62
La classe ArrayAlgsRiprendiamo la nostra classe ArrayAlgs
L'abbiamo introdotta quando abbiamo studiato semplici algoritmi su array
Contiene una collezione di metodi statici per l’elaborazione di array
• Per ora trattiamo array di numeri interi• Più avanti tratteremo generici array di Object
In particolare ArrayAlgs conterrà le realizzazioni dei vari algoritmi di ordinamento e ricerca da noi studiati È una “classe di utilità”, come la classe Math
63
Il metodo selectionSortpublic class ArrayAlgs{... public static void selectionSort(int[] v, int vSize) { for (int i = 0; i < vSize - 1; i++) { int minPos = findMinPos(v, i, vSize-1); if (minPos != i) swap(v, minPos, i); } } //abbiamo usato due metodi ausiliari, swap e findMinPos private static void swap(int[] v, int i, int j) { int temp = v[i]; v[i] = v[j]; v[j] = temp; } private static int findMinPos(int[] v, int from, int to) { int pos = from; int min = v[from]; for (int i = from + 1; i <= to; i++) if (v[i] < min) { pos = i; min = v[i]; } return pos; }...} 64
Ordinamento per selezioneL’algoritmo di ordinamento per selezione è corretto
ed è in grado di ordinare qualsiasi array allora perché studieremo altri algoritmi di
ordinamento? a cosa serve avere diversi algoritmi per risolvere
lo stesso problema?Vedremo che esistono algoritmi di ordinamento
che, a parità di dimensioni del vettore da ordinare, vengono eseguiti più velocemente
65
È tutto chiaro? …1.Perché nel metodo swap serve la variabile
temp? Cosa succede se si assegna semplicemente a[j] ad a[i] e a[i] ad a[j]?
2.Quali sono i passi compiuti da selectionSort per ordinare la sequenza 654321?
66
Rilevazione delle prestazioni
67
Rilevazione delle prestazioniLe prestazioni di un algoritmo vengono valutate in
funzione della dimensione dei dati trattati Per valutare l’efficienza di un algoritmo si misura il
tempo in cui viene eseguito su insiemi di dati di dimensioni via via maggiori
Il tempo non va misurato con un cronometro, perché parte del tempo reale di esecuzione non dipende dall’algoritmo caricamento della JVM caricamento delle classi del programma lettura dei dati dallo standard input visualizzazione dei risultati
68
Rilevazione delle prestazioni Il tempo di esecuzione di un algoritmo va misurato
all’interno del programmaSi usa il metodo statico
System.currentTimeMillis() che, ad ogni invocazione, restituisce un numero di
tipo long che rappresenta il numero di millisecondi trascorsi da un evento di
riferimento (la mezzanotte del 1 gennaio 1970)Ciò che interessa è la differenza tra due valori
si invoca System.currentTimeMillis( ) prima e dopo l’esecuzione dell’algoritmo (escludendo le operazioni di input/output dei dati)
69
La classe SelSortTesterimport java.util.Scanner;public class SelSortTester{ public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.print("Dimensione dell'array? "); int n = in.nextInt(); // costruisce un array casuale int[] a = ArrayAlgs.randomIntArray(n, 100); int aSize = a.length; // usa System.currentTimeMillis() per misurare il tempo long time = System.currentTimeMillis(); ArrayAlgs.selectionSort(a, aSize); time = System.currentTimeMillis() -time; System.out.println("Tempo trascorso: " + time + " ms"); }}
70
Rilevazione delle prestazioniEseguiamo l’ordinamento
di array con diverse dimensioni (n), contenenti numeri interi casuali
Si nota che l’andamento del tempo di esecuzione non è lineare se n diventa il doppio, il
tempo diventa circa il quadruplo!
71
Rilevazione delle prestazioniLe prestazioni dell’algoritmo di ordinamento per
selezione hanno quindi un andamento quadratico in funzione delle dimensioni dell’array
Le prossime domande che ci poniamo sono è possibile valutare le prestazioni di un algoritmo
al punto di vista teorico?• (ovvero senza realizzare un programma e senza
eseguirlo molte volte, per rilevarne i tempi di esecuzione ed osservarne l’andamento)
esiste un algoritmo più efficiente per l’ordinamento?
72
Analisi teorica delle prestazioni
73
Analisi teorica delle prestazioni Il tempo d’esecuzione di un algoritmo dipende da
numero e tipo di istruzioni macchina eseguite dal processore Che a loro volta dipendono in generale dalla
dimensione dei dati da elaborare• Ad esempio, nel caso di selectionSort, la lunghezza
dell’array da ordinareVogliamo stimare una funzione T(n) che descrive il
tempo di esecuzione T in funzione della dimensione n dei dati Tramite analisi teorica, senza esperimenti numerici Anzi, senza realizzare e compilare un algoritmo!
74
Analisi teorica delle prestazioniFacciamo alcune assunzioni ed alcune semplificazioni
drastiche Cerchiamo di stimare per eccesso il tempo di esecuzione
T(n), ovvero di ottenere una stima nel caso peggiore• Ad es., per un algoritmo di ordinamento il caso peggiore è
quello in cui l’array da ordinare è ordinato alla rovescia La stima di T(n) è ottenuta stimando il numero di
operazioni primitive di Java (o altro linguaggio ad alto livello) eseguite
• Assumiamo quindi che tutte le operazioni primitive di Java abbiano stessi tempi di esecuzione (anche se non è esattamente vero)
75
Analisi teorica delle prestazioniCosa si intende per “operazione primitiva”?Si intende una qualsiasi istruzione che abbia un tempo
di esecuzione (circa) costante. Ad esempio Istruzioni di assegnazione Operazioni aritmeriche o logiche Accessi ad elementi di un array ...
Ad esempio, nel caso di selectionSort facciamo un conteggio del numero di accessi in lettura o scrittura ad un elemento dell’array
76
Prestazioni di selectionSortEsaminiamo il codice java del metodo selectionSortContiamo gli accessi all’array nella prima iterazione
del ciclo esterno (ovvero per i=0) per trovare l’elemento minore si fanno n accessi per scambiare due elementi si fanno quattro accessi
• trascuriamo il caso in cui non serva lo scambio in totale, (n+4) accessi
A questo punto dobbiamo ordinare la parte rimanente, cioè un array di (n1) elementi serviranno quindi ((n1) + 4) accessi
E via così fino al passo con (n(n2))=2 elementi, incluso
77
Prestazioni di selectionSort Il conteggio totale degli accessi in lettura/scrittura è
quindiT(n) = (n+4)+((n-1)+4)+…+(3+4)+(2+4)
= n+(n-1)+…+3+2 + (n-1)*4
= n*(n+1)/2 - 1 + (n-1)*4
= 1/2*n2 + 9/2*n - 5Si ottiene quindi un’equazione di secondo grado in n, che giustifica l’andamento parabolico dei tempi rilevati sperimentalmente
n+(n-1)+…+3+2+1 = n*(n+1)/2
78
Andamento asintotico delle prestazioni
Facciamo un’ulteriore semplificazione, tenendo presente che ci interessano le prestazioni per valori elevati di n (andamento asintotico)
Se n vale 1000 1/2*n2 vale 500000 9/2*n - 5 vale 4495, circa 1% del totale
quindi diciamo che l’andamento asintotico dell’algoritmo in funzione di n è 1/2*n2
1/2*n2 + 9/2*n - 5
79
Andamento asintotico delle prestazioniFacciamo un’ulteriore semplificazione
ci interessa soltanto valutare cosa succede al tempo d’esecuzione T(n) se n, ad esempio, raddoppia
Nel caso in esame il tempo d’esecuzione quadruplica T(n) = 1/2*n2
T(2n) = 1/2*(2n)2 = 1/2*4*n2
= 4*T(n)Si osserva che T(2n) = 4*T(n)
In generale nel caso in cui T(n) = n2 Indipendentemente dal fatto che sia presente un
fattore moltiplicativo 1/2, o qualsiasi altro fattore moltiplicativo
1/2*n2
80
È tutto chiaro? …1.Se si aumenta di 10 volte la dimensione dei dati,
come aumenta il tempo richiesto per ordinare i dati usando selectionSort?
81
Notazione “Ogrande”Si dice quindi che
per ordinare un array con l’algoritmo di selezione si effettua un numero di accessi che è dell’ordine di n2
Per esprimere sinteticamente questo concetto si usa la notazione Ogrande e si dice che il numero degli accessi è O(n2)
Dopo aver ottenuto una formula che esprime l’andamento temporale dell’algoritmo, si ottiene la notazione “Ogrande” considerando soltanto il termine che si incrementa più rapidamente all’aumentare di n, ignorando coefficienti costanti
82
Notazione “Ogrande”, “ ”, “ ”Ω ΘLa notazione f(n)=O(g(n)) significa: f non cresce più
velocemente di g Ma è possibile che f cresca molto più lentamente Esempio: f(n) = n2 + 5n – 3 è O(n3), ma è anche O(n10)
Esistono ulteriori notazioni per descrivere il modo in cui una funzione cresce f(n)=Ω(g(n)) significa: f non cresce più lentamente di g
• Ovvero g(n) = O(f(n)) f(n)=Θ(g(n)) significa: f cresce con la stessa velocità di g
• Ovvero f(n) = O(g(n)) e f(n) = Ω(g(n))
83
Notazione “Ogrande”, “ ”, “ ”Ω Θ f(n) = O(g(n)) esiste una costante C>0 tale che
f(n)/g(n) < C definitivamente f(n) = Ω(g(n)) … f(n)/g(n) > C definitivamente f(n) = Θ(g(n)) … C1 < f(n)/g(n) < C2 definitivamente
84
Ordini di complessitàUn algoritmo può essere classificato in funzione delle
proprie prestazioni Un algoritmo è considerato efficiente se il suo tempo di
esecuzione (caso peggiore) è al più polinomiale Un algoritmo è considerato inefficiente se il suo tempo
di esecuzione (caso peggiore) è almeno esponenzialeUn problema algoritmico può essere classificato in
funzione della propria complessità (ovvero le prestazioni del più veloce algoritmo che lo risolve) Un problema è considerato trattabile se la sua
complessità è al più polinomiale Un problema è considerato non trattabile se la sua
complessità è almeno esponenziale
85
Ordini di complessitàSupponiamo che una istruzione di Java venga
eseguita in 106 s …
Un numero a 728 cifre di secoli
Un numero a 185 cifre di secoli
Un numero a 70 cifre di secoli
3.3 trilionidi anni
2.8 oren n
Un numero a 75 cifre di secoli
400 trilionidi secoli
35.7anni
1secondi
1/1000secondi2n
28.1 giorni
2.8ore
5.2minuti
3.2secondi
1/10secondin 5
9/100secondi
1/100secondi
1/400secondi
1/2500secondi
1/10000secondin 2
n=300n=100n=50n=20n=10f(n)
Prob
lem
i no
n tra
ttabi
liPr
oble
mi t
ratta
bili
(pol
inom
iali)
(1 anno 3E7 secondi)≈
86
Cicli annidati: analisi delle prestazioniRiesaminiamo la struttura di SelectionSort
È realizzato tramite due cicli annidati di questo tipo
Per stimare il tempo di esecuzione di due cicli annidati come questi dobbiamo stimare quante volte vengono eseguite le operazioni primitive nel ciclo più interno Per i = 0 vengono eseguite n volte Per i = 1 vengono eseguite n1 volte ... Quanto fa il totale??
for (int i = 0; i < n; i++)//... operazioni primitivefor (int j = i; j < n; j++)
//... operazioni primitive
87
Il totale delle operazioni primitive nel ciclo interno è
Quindi due cicli annidati del tipo appena esaminato hanno sempre prestazioni O(n2)
Dimostrazione di questa uguaglianza Basta disporre gli addendi in questo ordine
1 + 2 + 3 + ... + n/2 + n + (n-1) + (n-2) + ... + (n/2+1) ___________________________________ n+1 + n+1 + n+1 + ... + n+1
Cicli annidati: analisi delle prestazioni
n/2 volte
... = O(n2)
88
Ordinamento per fusione(MergeSort)
89
Presentiamo ora un algoritmo di ordinamento “per fusione” (MergeSort) che vedremo avere prestazioni migliori di quelle dell’ordinamento per selezione
Dovendo ordinare il vettore seguente
Lo dividiamo in due parti (circa) uguali
MergeSort
5 7 9 1 8
5 7 9 1 8
90
Supponiamo che le due parti siano già ordinate Allora è facile costruire il vettore ordinato, togliendo
sempre il primo elemento da uno dei due vettori, scegliendo il più piccolo
MergeSort
5 7 9 1 8 1
5 7 9 1 8 1 5
5 7 9 1 8 1 5 7
5 7 9 1 8 1 5 7 8
5 7 9 1 8 1 5 7 8 9
91
Ovviamente, nel caso generale le due parti del vettore non saranno ordinate
Possiamo però ordinare ciascuna parte ripetendo il processo dividiamo il vettore in due parti (circa) uguali supponiamo che siano entrambe ordinate uniamo le due parti nel modo appena visto
• questa fase si chiama fusione (merge)Continuando così, arriveremo certamente ad una
situazione in cui le due parti sono davvero ordinate quando contengono un solo elemento!
MergeSort
92
MergeSortSi delinea quindi un algoritmo ricorsivo per ordinare
un array, chiamato MergeSort Caso base: se l’array contiene meno di due elementi, è
già ordinato Altrimenti
• si divide l’array in due parti (circa) uguali• si ordina la prima parte usando MergeSort• si ordina la seconda parte usando MergeSort• si fondono le due parti ordinate usando l’algoritmo di
fusione (merge)
93
Realizzazione di mergeSortpublic class ArrayAlgs{ ... public static void mergeSort(int[] v, int vSize) { if (vSize < 2) return; // caso base int mid = vSize / 2; //dividiamo circa a meta’ int[] left = new int[mid]; int[] right = new int[vSize - mid]; System.arraycopy(v, 0, left, 0, mid); System.arraycopy(v, mid, right, 0, vSize-mid); // passi ricorsivi: ricorsione multipla (doppia) mergeSort(left, mid); mergeSort(right, vSize-mid); // fusione (metodo ausiliario) merge(v, left, right); } // continua
94
Realizzazione di mergeSort // continua private static void merge(int[] v, int[] v1, int[] v2) { int i = 0, i1 = 0, i2 = 0; while (i1 < v1.length && i2 < v2.length) if (v1[i1] < v2[i2]) // prima si usa i, poi lo si incrementa... v[i++] = v1[i1++]; else v[i++] = v2[i2++]; while (i1 < v1.length) v[i++] = v1[i1++]; while (i2 < v2.length) v[i++] = v2[i2++]; } ...}
95
È tutto chiaro? …1.Eseguire manualmente l’algoritmo mergeSort
sull’array 87654321
96
Prestazioni di MergeSort
97
Prestazioni di MergeSortRilevazioni sperimentali delle
prestazioni mostrano che l’ordinamento con MergeSort è molto più efficiente di quello con selectionSort
Cerchiamo di fare una valutazione teorica delle prestazioni Chiamiamo T(n) il numero di
accessi richiesti per ordinare un array di n elementi
98
Prestazioni di MergeSortLe due invocazioni di System.arraycopy richiedono
complessivamente 2n accessi tutti gli n elementi devono essere letti e scritti
Le due invocazioni ricorsive richiedono T(n/2) ciascuna
La fusione richiede n accessi per scrivere gli n elementi dell’array ordinato
• ogni elemento da scrivere richiede la lettura di due elementi, uno da ciascuno dei due array da fondere, per un totale di 2n accessi
99
Prestazioni di MergeSortSommando tutti i contributi si ottiene
T(n) = 2T(n/2) + 5nUn’equazione di questo tipo per T(n) viene detta
equazione di ricorrenzaLa soluzione di questa equazione per ottenere T(n) in
funzione di n non è semplice La troviamo per sostituzioni successive
T(n) = 2( 2T(n/4) + 5(n/2) ) + 5n = 4T(n/4) + 2*5n = = … = 2kT(n/2k) + k*5n
Se k = log2n, ovvero se 2k = n otteniamo T(n) = n + 5n*log2n
100
Prestazioni di MergeSortPer trovare la notazione “Ogrande” osserviamo che
il termine 5n*log2n cresce più rapidamente del termine n il fattore 5 è ininfluente, come tutte le costanti moltiplicative Nelle notazioni “Ogrande” non si indica la base dei
logaritmi, perché loga si può trasformare in logb con un fattore moltiplicativo, che va ignorato
In conclusione, le prestazioni dell’ordinamento MergeSort hanno un andamento
e sono quindi migliori di O(n2)
T(n) = n + 5n*log2n
T(n) = O(n log n)
101
Ordinamento per inserimento(cfr. argomenti avanzati 13.1)
102
Ordinamento per inserimentoL’algoritmo di ordinamento per inserimento
inizia osservando che il sottoarray di lunghezza unitaria costituito dalla prima cella dell’array è ordinato (essendo di lunghezza unitaria)
estende verso destra la parte ordinata, includendo nel sottoarray ordinato il primo elemento alla sua destra
• per farlo, il nuovo elemento viene spostato verso sinistra finché non si trova nella sua posizione corretta, spostando verso destra gli elementi intermedi
9 8 5 7 6a[0] a[1] a[2] a[3] a[4]
103
6
7
5
8
Ordinamento per inserimento
9 5 7 6 8 9 5 7 6
98 7 6 5 8 9 7 6
985 6 5 7 8 9 6
9875 5 6 7 8 9
= accesso in lettura = accesso in scrittura
104
Realizzazione di insertionSortpublic class ArrayAlgs{ ... public static void insertionSort(int[] v,int vSize) { // il ciclo inizia da 1 perché il primo // elemento non richiede attenzione for (int i = 1; i < vSize; i++) { int temp = v[i]; //nuovo el. da inserire // j va definita fuori dal ciclo perche` il // suo valore finale viene usato in seguito int j; //sposta di uno verso destra tutti gli el. a // sin. di temp e > di temp, partendo da destra for (j = i; j > 0 && temp < v[j-1]; j--) v[j] = v[j-1]; v[j] = temp; // inserisci temp } } ...}
105
Prestazioni di insertionSortOrdiniamo con inserimento un array di n elementi Il ciclo esterno esegue n-1 iterazioni
ad ogni iterazione vengono eseguiti• 2 accessi (uno prima del ciclo interno ed uno dopo)• il ciclo interno
Il ciclo interno esegue 3 accessi per ogni sua iterazione ma quante iterazioni esegue?
• dipende da come sono ordinati i dati!
106
Prestazioni di insertionSortCaso peggiore: i dati sono ordinati a rovescioCiascun nuovo elemento inserito richiede lo
spostamento di tutti gli elementi alla sua sinistra, perché deve essere inserito in posizione 0T(n) = (2 + 3*1) + (2 + 3*2) +
(2 + 3*3) + ... + (2 + 3*(n-1)) = 2(n-1) + 3[1+2+...+(n-1)] = 2(n-1) + 3n(n-1)/2 = O(n2)Osservazione: la struttura di insertionSort è quella dei
due cicli annidati esaminati in precedenza (analoga a quella di selectionSort)
107
Prestazioni di insertionSortCaso migliore: i dati sono già ordinati Il ciclo più interno non esegue mai iterazioni
richiede un solo accesso per la prima verifica Il ciclo esterno esegue n-1 iterazioni
ad ogni iterazione vengono eseguiti• 2 accessi (uno prima del ciclo interno ed uno dopo)• 1 accesso (per verificare la condizione di terminazione
del ciclo interno)T(n) = 3*(n-1) = O(n)
108
Prestazioni di insertionSortCaso medio: i dati sono in ordine casualeCiascun nuovo elemento inserito richiede in media
lo spostamento di metà degli elementi alla sua sinistra
T(n) = (2 + 3*1/2) + (2 + 3*2/2) + (2 + 3*3/2) + ... + (2 + 3*(n-1)/2) = 2(n-1) + 3[1+2+...+(n-1)]/2 = 2(n-1) + 3[n(n-1)/2]/2 = O(n2)
109
Confronto tra ordinamenti
Se si sa che l’array è “quasi” ordinato, è meglio usare l’ordinamento per inserimento
Esempio notevole: un array che viene mantenuto ordinato per effettuare ricerche, inserendo ogni tanto un nuovo elemento e poi riordinando
casomigliore
casomedio
casopeggiore
mergesort
n lg n n lg n n lg n
selectionsort
n2 n2 n2
insertionsort n n2 n2
110
È tutto chiaro? …1.Eseguire manualmente l’algoritmo insertionSort
sull’array 87654321 e sull’array 23456781
111
Ricerca lineare
112
Ricerca lineareAbbiamo già visto un algoritmo da utilizzare per
individuare la posizione di un elemento che abbia un particolare valore all’interno di un array i cui elementi non siano ordinati
Dato che bisogna esaminare tutti gli elementi, si parla di ricerca sequenziale o lineare
public class ArrayAlgs{ ... public static int linearSearch(int[] v, int vSize, int value) { for (int i = 0; i < vSize; i++) if (v[i] == value) return i; // trovato valore return -1; // valore non trovato } ...}
113
Ricerca lineare: prestazioniValutiamo le prestazioni dell’algoritmo di ricerca
lineare se l’elemento cercato non è presente nell’array, sono
sempre necessari n accessi se l’elemento cercato è presente nell’array, il numero di
accessi necessari per trovarlo dipende dalla sua posizione
• Nel caso peggiore cominciamo a cercare dal primo indice dell’array, e l’elemento cercato si trova nell’ultima posizione: sono necessari n accessi.
• In media gli accessi saranno n/2 In ogni caso, quindi, le prestazioni dell’algoritmo sono
O(n)114
È tutto chiaro? …1.Si immagini di cercare con linearSearch un
numero telefonico in un array di 1000000 di dati. Quanti dati vanno esaminati mediamente per trovare il numero?
115
Ricerca binaria
116
Ricerca in un array ordinato Il problema di individuare la posizione di un
elemento all’interno di un array può essere affrontato in modo più efficiente se l’array è ordinato Esempio: Cerchiamo l’elemento 12 in questo array
Confrontiamo 12 con l’elemento che si trova (circa) al centro dell’array, a[2], che è 11
L’elemento che cerchiamo è maggiore di 11• se è presente nell’array, allora sarà a destra di 11
125 9 11 17a[0] a[1] a[2] a[3] a[4]
21a[5]
117
125 9 11 17a[0] a[1] a[2] a[3] a[4]
21a[5]
Ricerca in un array ordinato
A questo punto dobbiamo cercare l’elemento 12 nel solo sottoarray che si trova a destra di a[2] Usiamo lo stesso algoritmo, confrontando 12 con
l’elemento che si trova al centro, a[4], che è 17 L’elemento che cerchiamo è minore di 17
• se è presente nell’array, allora sarà a sinistra di 17
118
A questo punto dobbiamo cercare l’elemento 12 nel sottoarray composto dal solo elemento a[3] Usiamo lo stesso algoritmo, confrontando 12 con
l’elemento che si trova al centro, a[3], che è 12 L’elemento che cerchiamo è uguale a 12
• l’elemento che cerchiamo è presente nell’array e si trova in posizione 3
125 9 11 17a[0] a[1] a[2] a[3] a[4]
21a[5]
Ricerca in un array ordinato
119
Se il confronto tra l’elemento da cercare e l’elemento a[3] avesse dato esito negativo avremmo cercato nel sottoarray vuoto a sinistra o a
destra concludendo che l’elemento cercato non è presente
nell’arrayQuesto algoritmo si chiama ricerca binaria
perché ad ogni passo si divide l’array in due parti• funziona soltanto se l’array è ordinato
125 9 11 17a[0] a[1] a[2] a[3] a[4]
21a[5]
Ricerca in un array ordinato
120
Realizzazione di binarySearchpublic class ArrayAlgs{ ... public static int binarySearch(int[] v, int vSize, int value) { return binSearch(v, 0, vSize-1, value); } private static int binSearch(int[] v, int from, int to, int value) { if (from > to) return -1;// caso base: el. non trovato int mid = (from + to) / 2; // mid e` circa in mezzo int middle = v[mid]; if (middle == value) return mid; // caso base: elemento trovato else if (middle < value) //cerca a destra return binSearch(v, mid + 1, to, value); else // cerca a sinistra return binSearch(v, from, mid - 1, value); } //ATTENZIONE: e` un algoritmo con ricorsione SEMPLICE ...}
121
Prestazioni di binarySearchValutiamo le prestazioni dell’algoritmo di ricerca
binaria in un array ordinato osserviamo che l’algoritmo è ricorsivo
Per cercare in un array di dimensione n bisogna effettuare un confronto (con l’elemento centrale) effettuare una ricerca in un array di dimensione n/2
Quindi
Analogamente all’analisi delle prestazioni di mergeSort, l’equazione per T(n) che abbiamo trovato è una equazione di ricorrenza
T(n) = T(n/2) + 1
122
Prestazioni di binarySearch
Come nel caso di mergeSort, troviamo la soluzione per sostituzioni successive T(n) = (T(n/4) + 1 ) + 1 = T(n/4) + 2 = = … = T(n/2k) + k
Se k = log2n, ovvero se 2k = n otteniamo T(n) = T(1) + log2n = 1 + log2n
Quindi le prestazioni sono E sono migliori di quelle della ricerca lineare
T(n) = T(n/2) + 1
O(log n)
123
È tutto chiaro? …1.Si immagini di cercare con binarySearch un
numero telefonico in un array ordinato di 1000000 di dati. Quanti dati vanno esaminati mediamente per trovare il numero?
124
Approfondimento per gli interessatiAnalisi delle prestazioni di
recursiveFib
125
Prestazioni di recursiveFibQualche tempo fa abbiamo scritto un metodo
ricorsivo per calcolare i numeri di Fibonacci Abbiamo verificato sperimentalmente che per n>30 il
calcolo non è più istantaneo E abbiamo visto perché: il metodo ricalcola più volte
(inutilmente) valori già calcolatipublic static long recursiveFib(int n){ if (n < 1) throw new IllegalArgumentException(); long f; if (n < 3) f = 1; else f = recursiveFib(n-1) + recursiveFib(n-2); return f;}
126
Prestazioni di recursiveFibStimiamo il tempo T(n) necessario a calcolare fib(n)
Poiché l’algoritmo è ricorsivo, proviamo a cercare una equazione di ricorrenza
Per calcolare fib(n) devo calcolare fib(n1) e fib(n2)Quindi
T(n) = T(n1) + T(n2) > 2T(n2) > 2[2T(n4)] > … > 2kT(n2k) > 2n/2
Come avevamo anticipato, le il tempo di esecuzione dell’algoritmo fib è esponenziale in n
127
Approfondimento per gli interessatiComplessità del problema delle
torri di Hanoi
128
Complessità di HanoiQualche tempo fa abbiamo scritto una soluzione
ricorsiva al problema delle torri di HanoiStimiamo il numero di mosse T(n) necessarie a trovare
la soluzione per il problema a n dischi. Bisogna Risolvere il problema di dimensione n1 Spostare un disco Risolvere nuovamente il problema di dimensione n1
T(n) è dato da una equazione di ricorrenzaT(n) = 2T(n1) + 1 = 2*(2T(n2) +1) +1 = 4T(n2) +(1+2)
= … = 2kT(nk) + (1+2+…+2k1) = 2n1 + (1+2+…+2n2 )Questa è una serie geometrica: (1+2+…+2n1 ) = 2n 1Come avevamo anticipato, T(n) = 2n – 1
129
Complessità di HanoiQuanto tempo impiegheranno i monaci di Hanoi a
spostare i 64 dischi sacri? Supponiamo che spostino un disco al secondo Supponiamo che non sbaglino neanche una volta
Il tempo impiegato èT(n) = (264 1) s 10≈ 18 * 24 s = 1.6E19 s
(perché 210 10≈ 3) Inoltre 1 anno 3E7 s≈Allora:
T(n) 5.8E11 anni≈ , ovvero 580 miliardi di anni130