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

Modello di costo

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

Operazioni primitive

• Numero di operazioni: Il numero di passi base eseguite dall'algoritmo (ad esempio, istruzioni macchina del processore).
• Dimensione dei dati: Ad esempio, la lunghezza dell’array da ordinare.
• Valore dei dati: Ad esempio, un array già ordinato, ordinato al contrario, con valori casuali, ecc.

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

Operazione primitiva

Cosa si intende per operazione primitiva (passo base)? È una operazione che ha tempo di esecuzione (circa) costante, indipendente da valori e tipi dei dati. Esempi includono:

• Assegnazione di valore ad una variabile
• Operazione aritmetica o logica tra variabili e/o costanti numeriche e booleane
• Accesso in lettura/scrittura ad un elemento di un array

Un enunciato contenente una invocazione di un metodo non è un'operazione primitiva.

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 dell'array (dimensione dei dati del problema).

Dimensione dei dati

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

Indipendentemente dal tipo di dati, indichiamo sempre con n la dimensione dell'input.

Valore dei dati

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 il caso peggiore, ovvero si cerca di ottenere una stima “di eccesso”. Ad esempio, per un algoritmo di ordinamento il caso peggiore è quello in cui l’array in input è ordinato alla rovescia.

Si possono anche fare stime di:

• Caso migliore: Ad esempio, array in input già ordinato.
• Caso medio: Con ipotesi statistiche, ad esempio, 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.