Informatica I - l'analisi teorica delle prestazioni di un programma

Modello di costo: il tempo d'esecuzione di un algoritmo

Il tempo d'esecuzione di un algoritmo dipende in generale dai seguenti fattori:

1. Il numero di operazioni primitive (o passi base) eseguite dall'algoritmo (ad esempio, istruzioni macchina del processore)
2. La dimensione dei dati da elaborare (ad esempio, la lunghezza dell'array da ordinare)
3. Il valore dei dati da elaborare (ad esempio, un array già ordinato, ordinato al contrario, con valori casuali, ...)

Dato un algoritmo, vogliamo stimare una funzione T(n) che ne descrive il tempo di esecuzione T unicamente in funzione della dimensione n dei suoi dati senza realizzare e compilare un algoritmo base.

1. Cosa si intende per operazione primitiva (passo base)?

È una operazione che ha tempo di esecuzione (circa) costante, ed è indipendente dai valori e tipi dei dati. (Esempio: assegnazione di valore ad una variabile, operazione aritmetica o logica tra variabili e/o costanti numeriche e booleane, un accesso in lettura/scrittura ad un elemento di un array). Un enunciato

contenente una invocazione di un metodo non è un'operazione primitiva. selectionSort. Nel caso di selectionSort, il tempo di esecuzione si stima contando il numero di accessi in lettura/scrittura ad un elemento dell'array, in funzione della lunghezza nell'array (dimensione dei dati del problema). 2. Cosa si intende per dimensione dei dati di un algoritmo? A seconda del problema, la dimensione dell'input assume significati diversi: - La grandezza di un numero (ad esempio in problemi di calcolo) - Il numero di elementi su cui lavorare (ad esempio in problemi di ordinamento) - Il numero di bit che compongono un numero - n Indipendentemente dal tipo di dati, indichiamo sempre con la dimensione dell'input. 3. Come si tiene conto del valore dei dati? Se l'algoritmo contiene cicli e decisioni, il numero di operazioni primitive dipende anche dal valore dei dati, ma noi vogliamo T(n) come funzione solo di n. Di solito si stima T(n) per caso peggiore, ovvero si cerca di

ottenere una stima “di (Ad es. per un algoritmodi ordinamento il caso peggiore è quello in cui l’array in input è ordinato alla rovescia).caso migliore casoSi possono anche fare stime di: (ad es. array in input già ordinato) omedio (con ipotesi statistiche, ad es. array contenente numeri casuali)Esempio:Esaminiamo il codice Java del metodo selectionSort:

• Conteggio degli 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
• Caso peggiore: ipotizziamo che serva sempre lo scambio. In totale si fanno quindi (n+4) accessi
• Ora l'algoritmo deve ordinare la parte rimanente, cioè un array di (n-1) elementi serviranno quindi ((n-1) + 4) accessi
• E così fino al passo con (n-(n-2))=2 elementi, incluso