Orale Fondamenti di Informatica

R ICORSIONE E ARRAY

Per gestire gli array in modo ricorsivo

• in genere la ricorsione non viene effettuata sugli array

• ma piuttosto sugli indici usati per accedere l’array

Ricerca binaria

L’algoritmo di ricerca binaria, consente di effettuare la ricerca di un elemento in un array ordinato in

modo crescente. Per effettuare la ricerca di una chiave entro un certo spazio di ricerca è possibile

ragionare in modo ricorsivo:

• se lo spazio di ricerca è vuoto, allora la ricerca si conclude con esito negativo

• se lo spazio di ricerca non è vuoto e l’elemento centrale dello spazio di ricerca è uguale alla

chiave, la ricerca si conclude con esito positivo: la posizione dell’elemento trovato è quella

dell’elemento centrale

• se lo spazio di ricerca non è vuoto e l’elemento centrale dello spazio di ricerca è minore

della chiave, la ricerca può proseguire, rimuovendo dallo spazio di cerca l’elemento

centrale e tutti quelli alla sua sinistra

• se lo spazio di ricerca non è vuoto e l’elemento centrale dello spazio di ricerca è maggiore

della chiave, allora la ricerca può proseguire, rimuovendo dallo spazio di ricerca l’elemento

centrale e tutti quelli alla sua destra

// Ricerca chiave nell'array ordinato in modo crescente, restituendo l'indice di un elemento

di uguale chiave (oppure -1).

implementazione ricorsiva della ricerca binaria.

public static int ricercaBinaria(int[] a, int chiave) {

// pre: a!=null &&

// a è ordinato in modo crescente

/* cerca chiave tra tutti gli elementi di a */

return ricBinRic(a, chiave, 0, a.length);

}

/* Verifica se a contiene un elemento uguale a chiave

* di indice tra sinistra (compreso) e destra (escluso). */

private static int ricBinRic(int[] a, int chiave, int sinistra,

int destra) { // posizione di un elemento di a di uguale a chiave, se esiste

int posizione; // indice dell'elemento centrale dello spazio di ricerca

int centro;

/* cerca l'indice di un elemento di a, tra sinistra e destra, uguale a chiave */

centro = (sinistra+destra)/2;

// la ricerca è fallita

if (sinistra>=destra)

posizione = -1; // trovato!

else if (a[centro]==chiave)

posizione = centro; // continua a sinistra

else if (a[centro]>chiave)

posizione = ricBinRic(a, chiave, sinistra, centro);

// continua a destra

else posizione = ricBinRic(a, chiave, centro+1, destra);

return posizione;

}

Complessità CAP 23

Intuitivamente un metodo è tanto più efficiente quanto minori sono le risorse di calcolo necessarie

per la sua esecuzione. Tra le risorse di calcolo la più pregiata è il processore, il cui impiego è

quantificato come tempo di esecuzione; da questo punto di vista un metodo è tanto più efficiente

quanto minore è il tempo richiesto per la sua esecuzione.

Il tempo di esecuzione di un metodo dipende:

• Dall’insieme di dati di ingresso usati nell’esecuzione del metodo . Ad esempio il tempo di

esecuzione impiegato da un metodo che calcola il fattoriale di un numero naturale dipende

dal numero usato come argomento, mentre il tempo richiesto da un metodo che calcola il

massimo tra gli elementi di un array di interi, dipende sia dal numero degli elementi

dell’array che dal loro valore.

• Dipende anche da fattori tecnologici , come il tipo di computer usato oppure il carico del

computer durante l’esecuzione del metodo.

L’analisi di complessità di metodo ha lo scopo di determinare una funzione, chiamata funzione di

costo del metodo, che stima il tempo di esecuzione del metodo in modo parametrico rispetto

all’insieme di dati di ingresso usati per l’esecuzione. Si tratta di una stima in cui vengono ammesse

alcune approssimazioni; ad esempio vengono trascurate la dipendenza da fattori come il computer

usato. La funzione di costo di un metodo non viene espressa in termini di unità di tempo, ma come

numero di operazioni elementari che vanno svolte.

La funzione di costo di un metodo ha questo nome perché il tempo richiesto dalla sua esecuzione

viene considerato un costo, chiamato costo computazionale o complessità computazionale del

metodo. La funzione di costo viene calcolata considerando unitario il costo speso nell’esecuzione

di ciascuna operazione elementare (assegnazione, condizione o istruzione semplice) e calcolando

il costo speso nell’esecuzione di istruzioni più complesse (istruzioni ripetitive) come somma dei

costi dell’esecuzione delle sue componenti.

La teoria della complessità computazionale studia le risorse minime necessarie (principalmente

tempo di calcolo e memoria) per la risoluzione di un problema.

In informatica, la complessità temporale di un algoritmo quantifica la quantità di tempo impiegata

da un algoritmo a essere eseguito in funzione della grandezza dell’input. La complessità temporale

di un algoritmo è espressa comunemente usando la notazione O-grande, che esclude i coefficienti

e i termini di ordine inferiore. Quando è espressa in questo modo, si dice che la complessità

temporale è descritta asintoticamente, ossia, quando la dimensione degli input va a infinito. Ad 3

esempio, se il tempo richiesto da un algoritmo su tutti gli input di dimensione n è al massimo 5n +

3

3n, la complessità temporale asintotica è O(n ).

La complessità temporale è stimata comunemente contando il numero di operazioni elementari

eseguite dall'algoritmo, dove un'operazione elementare impiega una quantità di tempo fissa a

essere eseguita. Così la quantità di tempo impiegata e il numero di operazioni elementari eseguite

dall'algoritmo differiscono al massimo di un fattore costante.

Poiché il tempo di esecuzione di un algoritmo può variare con diversi input della stessa

dimensione, si usa comunemente la complessità temporale del caso peggiore di un algoritmo,

denotata come T(n), che è definita come la quantità di tempo massimo impiegata su qualsiasi input

di dimensione n. Le complessità temporali sono classificate in base alla natura della funzione T(n).

Ad esempio, un algoritmo con T(n) = O(n) è chiamato algoritmo in tempo lineare, e un algoritmo

n

con T(n) = O(2 ) si dice che è un algoritmo in tempo esponenziale.

La complessità spaziale è la quantità di risorse necessarie all'algoritmo per l'elaborazione. È

solitamente misurata in termini di byte di memoria necessari per memorizzare le informazioni

temporanee nel corso dell'esecuzione dell'algoritmo. In genere la complessità spaziale è minore di

quella temporale.

static int sommaArray(int[] a){

// restituisce la somma degli elementi dell'array a

int somma=0;

for (int i=0; i<a.length; i++){

somma += a[i];

}

return somma;

}

In questo caso l’analisi di complessità consente di determinare una funzione di costo

t N

( ) che esprime il numero di operazioni elementari richieste dall’esecuzione del

sommaArray t N

( )=3N +4

metodo quando l’array a ha lunghezza N. Risulta che .

somm aArray

• L’assegnazione somma=0 è un’operazione elementare con costo unitario. L’esecuzione di

somma è indipendente dal valore di N, il suo contributo alla funzione di costo è 1.

• L’esecuzione del for inizia con l’esecuzione della sua inizializzazione i=0 : operazione

elementare eseguita una sola volta, indipendentemente dal valore di N. Il suo contributo è

di 1.

• L’esecuzione del for richiede N esecuzioni del suo corpo, che è formato dalla sola

assegnazione somma+=a[i], che è un’operazione elementare; ciascuna operazione ha

costo unitario, ma il costo complessivo è N.

• Nell’esecuzione del for, il corpo viene eseguito N volte; pertanto la sua condizione

i<a.lenght viene valutata N+1 volte poiché anche la valutazione della condizione è

un’operazione elementare

• L’esecuzione del for richiede anche N esecuzioni del suo aggiornamento i++, anch’essa

operazione elementare con contributo N

• Infine anche l’istruzione return somma è un’operazione elementare che ha costo unitario,

eseguita una sola volta indipendentemente da N; il suo contributo è di costo 1.

t N N N N 4

( )=1+1+ ( )

+ +1 + +1=3N+

somm aArray

La valutazione della funzione di costo di un metodo è guidata dalle modalità seguite nella sua

determinazione che possono essere espresse sotto forma di modello di costo.

Ogni possibile modello di costo introduce comunque delle approssimazioni, ad esempio, il

semplice modello di costo considerato assegna costo computazionale 1 a qualsiasi operazione

elementare

In genere il costo computazionale di un metodo dipende non solo dalla dimensione dei suoi dati in

ingrasso, ma anche dal valore dei suoi dati in ingresso. Nell’analisi di complessità la dipendenza di

una funzione di costo dal valore dei dati in ingresso non è solitamente gradita. L’approccio seguito

consiste nel determinare la funzione di costo nel caso peggiore , esprimendo il costo massimo di

esecuzione del metodo, in modo parametrico rispetto alla sola dimensione dei dati in ingresso.

C OMPLESSITÀ ASINTOTICA

Il calcolo esatto della funzione di costo di un metodo, in cui viene determinato il numero esatto di

volte in cui ciascuna delle sue operazioni elementari viene eseguita è molto laborioso. Ciò che

spesso interessa è solo come il costo computazionale di un metodo cresce al crescere della

dimensione dei suoi dati in ingresso. Ad esempio è sufficiente sapere che la funzione di costo

t N

( ) di un metodo che calcola la somma degli elementi di un array di interi cresce

somm aArray

linearmente con la lunghezza N dell’array.

T N

( )

La funzione di costo asintotico di un metodo M descrive l’ordine di grandezza del

M

costo di esecuzione di M in funzione della dimensione N dei suoi dati in ingresso. (Viene usata la

convenzione di indicare con la t minuscola la funzione che descrive il costo esatto di un metodo, e

T N

( )=N

con T maiuscola quella che ne descrive il costo asintotico). .

somm aArray

L’analisi asintotica di complessità si pone l’obiettivo di

• determinare la funzione di costo in modo asintotico, ovvero a meno di fattori moltiplicativi

costanti

• a meno di termini additivi di ordine inferiore

• descrivendo l’andamento della funzione di costo per N (la dimensione dei dati di ingresso)

tendente all’infinito t N

( ) =3N +4

Ad esempio nella funzione , il 3 è