Algoritmi

Algoritmi

Efficienza di un algoritmo

Nel valutare l’efficienza di un algoritmo bisogna considerare 2 fattori:
• Il tempo di esecuzione di un algoritmo
• Lo spazio di memoria richiesto dall’esecuzione
Entrambi i fattori sono importanti ma generalmente ci si concentra sul primo fattore.
• Algoritmi di ordinamento
Gli algoritmi di ordinamento consistono nel scambiare gli elementi presenti in una struttura dati (es.

Array) in modo da disporli in ordine crescente o decrescente.
1. Bubble Sort
Algoritmo per scambio, lavora con 2 elementi, occorrono N scansioni quanto gli elementi – 1. Si basa sull’idea di far emergere pian piano gli elementi più piccoli verso l’inizio dell’insieme da ordinare facendo sprofondare quelli maggiori verso il fondo. La strategia è quella di scorrere più volte la sequenza da ordinare, verificando ad ogni passo l’ordinamento reciproco degli elementi contigui (vicini) e scambiarli eventualmente di posizione se non ordinati. In C++:
2. Selezione
Questo algoritmo seleziona l’elemento più piccolo dell’array e lo pone in prima posizione.
ES. 20 33 17 2 -> 2 33 17 20 -> 2 17 33 20 -> 2 17 20 33.
Il tempo di esecuzione è uguale sia nel caso migliore (già ordinato) che nel caso peggiore.
3. Inserimento
Questo algoritmo consiste nell’inserire un elemento alla volta nella posizione che gli spetta, spostando verso destra gli altri elementi.
Il tempo di esecuzione è proporzionale al numero di confronti che si effettuano durante l’esecuzione.

• Algoritmi di ricerca
Ricercare un elemento in un vettore significa individuare la posizione (i) che questa assume all’interno di un vettore se è presente.

1. Ricerca sequenziale
Questo algoritmo effettua una scansione sequenziale dell’array. Si possono verificare 3 situazioni:
1° situazione: dire se un elemento è presente oppure no.
2° situazione: dire se un elemento è presente almeno una volta nel vettore.
3° situazione: dire quante volte è presente un elemento nel vettore.

2. Ricerca binaria
Per usare questo algoritmo, il vettore deve essere ordinato. Il numero da ricercare nel vettore di N elementi viene confrontato con l’elemento centrale del vettore (n/2). Si possono verificare 3 situazioni:
1° situazione: il numero da ricercare è minore dell’elemento centrale, quindi il numero si deve cercare nella prima metà del vettore.
2° situazione: il numero da ricercare è uguale all’elemento centrale.
3° situazione: il numero da ricercare è maggiore dell’elemento centrale, quindi il numero si deve cercare nella seconda metà del vettore.
Per scrivere questo algoritmo bisogna porsi nella situazione peggiore. Questo algoritmo rientra nella famiglia di algoritmi che sfruttano la strategia del “DIVIDE ET IMPERA” e riducono la complessità dell’algoritmo effettuando la suddivisione progressiva della dimensione del problema in due parti, cioè applicando la riduzione di dicotomica (=in 2), ogni iterazione infatti dimezza il numero degli elementi che bisogna confrontare, mentre nell’algoritmo sequenziale diminuiva di un elemento.
Descrizione dell’algoritmo
1. Individuare l’elemento in posizione centrale. (pos. Iniziale + pos. Finale) /2
2. Effettuare il confronto. N=V[medio]:
a) Se si, terminare la ricerca e trovato=true;
b) Se N> V[medio] riduciamo il vettore alla 2° metà, INIZIO= medio + 1;
c) Se N Si ripete finché Inizio=fine.