GLI ALGORITMI

Gli algoritmi

Qual è il più veloce?

Start

Sommario

Introduzione

Distinzione degli algoritmi

Conclusioni

L'esperimento

Introduzione

Cos'è un algoritmo

Un algoritmo è una sequenza logica di istruzioni elementari che, eseguite in un ordine stabilito, permettono la soluzione di un problema in un numero finito di passi.

Distinzione degli algoritmi

Ricerca e ordinamento

Gli algoritmi che analizzeremo vengono categorizzati in due gruppi distinti: ricerca e ordinamento di vettori.

Ricerca dicotomica

Ricerca sequenziale

Quick sort

Ordinamento sequenziale

Ordinamento a bolle

L'esperimento

In cosa consiste

Qualsiasi programma richiede spazio di memoria e tempo di calcolo e in base all’utilizzo di questi esistono algoritmi più semplici e altri più complessi.

Per calcolare la complessità degli algoritmi ci concentreremo sul tempo impiegato e questo ci permette di scegliere tra loro quello più efficiente (a minor complessità temporale).

L’esperimento consiste nel fare una serie di prove per ogni algoritmo su vettori di diverse dimensioni, dove i dati di base saranno le medie di ogni tipo di prova.Successivamente bisogna mettere a confronto i dati ottenuti dall’esperimento degli algoritmi di ogni gruppo separatamente per capire quale di essi è il più efficiente.

L'algoritmo utilizzato per il tempo

// Misura l'orario di inizio clock_gettime(CLOCK_MONOTONIC, &start);

// Calcola il tempo trascorso in nanosecondi elapsed_time = (end.tv_sec - start.tv_sec) * 1000000000 + (end.tv_nsec - start.tv_nsec);

// Stampa il tempo impiegato per l'ordinamento printf("\nNumero elementi %d, Prova %d - Tempo di ordinamento sequenziale per il minimo: %lld nanosecondi", k, j + 1, elapsed_time);

// Calcola la media del tempo di ordinamento per le prove somma = somma / 1000000; double media = 1.0 * somma / numeroProve; printf("\nMedia prove = %f millisecondi", media); } return 0; }

L'algoritmo utilizzato per la media prove

I DATI

Ricerca dicotomica

Ricerca sequenziale

I DATI

Ordinamento sequenziale

Bubble sort

Quick sort

I GRAFICI

Conclusioni

Grazie all’esperimento effettuato abbiamo visto che ci possono essere più algoritmi che risolvono uno stesso problema e per questo bisogna capire quale sia il più efficace. Possiamo valutare l’efficacia dell’algoritmo in base alla sua semplicità e in base all’utilizzo di risorse.

Secondo i grafici l'algoritmo più efficiente è

La ricerca dicotomica

(per gli algoritmi di ricerca)

Secondo i grafici l'algoritmo più efficiente è

Il quick-sort

(per gli algoritmi di ordinamento)

Grazie per l'attenzione!

Informazioni prese da: Wikipedia, Università di Bologna

Start