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(1­1)! = 1∙0! = 1∙1 = 1  2! = 2(2­1)! = 2∙1! = 2∙1 = 2  3! = 3(3­1)! = 3∙2! = 3∙2∙1 = 6  4! = 4(4­1)! = 4∙3! = 4∙3∙2∙1 = 24  5! = 5(5­1)! = 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 n­1, 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 i­esimo carattere? Concatenando l’i­esimo carattere con tutte le 

permutazioni della stringa composta dai rimanenti N­1 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 pre­condizioni

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 N­1 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’i­esimo 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.length­1 l’indice vale

i*subperm.length +subperm.length­1 =  (i+1)*subperm.length ­1

Per i =word.length()­1, j =subperm.length­1, 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.length­1 (perché i vale 0)

Alla seconda iterazione di i, l’indice varia tra 1*subword.length+0 = subword.length1*subword.length+shorterword.length­1 =

                                                2*subword.length­1Si 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 n­1 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 n­1 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 (n­1) elementi serviranno quindi ((n­1) + 4) accessi

E via così fino al passo con (n­(n­2))=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 “O­grande”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 O­grande 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 “O­grande” considerando soltanto il termine che si incrementa più rapidamente all’aumentare di n, ignorando coefficienti costanti

82

Notazione “O­grande”, “ ”, “ ”Ω Θ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 “O­grande”, “ ”, “ ”Ω Θ 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 10­6 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 n­1 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 “O­grande” osserviamo che

il termine 5n*log2n cresce più rapidamente del termine n  il fattore 5 è ininfluente, come tutte le costanti moltiplicative Nelle notazioni “O­grande” 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 sotto­array 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 sotto­array 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 sotto­array 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(n­1) e fib(n­2)Quindi

T(n) = T(n­1) + T(n­2) > 2T(n­2) > 2[2T(n­4)] > … > 2kT(n­2k) > 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 n­1 Spostare un disco Risolvere nuovamente il problema di dimensione n­1

T(n) è dato da una equazione di ricorrenzaT(n) = 2T(n­1) + 1 = 2*(2T(n­2) +1) +1 = 4T(n­2) +(1+2)

 = … = 2kT(n­k) + (1+2+…+2k­1) = 2n­1 + (1+2+…+2n­2 )Questa è una serie geometrica: (1+2+…+2n­1 ) = 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