Concetti Chiave
- La valutazione dell'efficienza di un algoritmo si basa principalmente sul tempo di esecuzione e sullo spazio di memoria richiesto.
- Gli algoritmi di ordinamento come Bubble Sort, Selezione e Inserimento seguono strategie diverse per organizzare gli elementi in ordine crescente o decrescente.
- La ricerca sequenziale esegue una scansione dell'array per determinare la presenza e la frequenza di un elemento, gestendo diverse situazioni di ricerca.
- La ricerca binaria, che richiede un vettore ordinato, dimezza il problema ad ogni iterazione, migliorando l'efficienza rispetto alla ricerca sequenziale.
- Ogni algoritmo presenta complessità diverse e tempi di esecuzione variabili, influenzati dal numero di confronti effettuati e dalla strategia utilizzata.
Quali sono i fattori di efficienza degli algoritmi?
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
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.
Domande da interrogazione
- Quali sono i principali fattori da considerare per valutare l'efficienza di un algoritmo?
- Come funziona l'algoritmo Bubble Sort?
- Qual è la caratteristica principale dell'algoritmo di selezione?
- In cosa consiste l'algoritmo di ricerca binaria e quali sono le sue condizioni?
- Quali situazioni può gestire l'algoritmo di ricerca sequenziale?
I principali fattori da considerare sono il tempo di esecuzione e lo spazio di memoria richiesto dall'esecuzione, con una maggiore attenzione generalmente rivolta al tempo di esecuzione.
Il Bubble Sort lavora scambiando due elementi alla volta, facendo emergere gli elementi più piccoli verso l'inizio dell'array e spingendo quelli maggiori verso il fondo, richiedendo N scansioni per ordinare.
L'algoritmo di selezione trova l'elemento più piccolo dell'array e lo posiziona in prima posizione, mantenendo lo stesso tempo di esecuzione sia nel caso migliore che nel caso peggiore.
La ricerca binaria richiede un vettore ordinato e confronta il numero da ricercare con l'elemento centrale, riducendo progressivamente la dimensione del problema, dimezzando il numero di elementi da confrontare ad ogni iterazione.
L'algoritmo di ricerca sequenziale può determinare se un elemento è presente, se è presente almeno una volta e quante volte è presente nel vettore.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
