Sommario

• Modello di costo dei programmi/algoritmi
• Costo dei programmi: la notazione O
• Algoritmi di ricerca (ricerca sequenziale, ricerca binaria)

Costo di un programma

Problema: dato un array a di interi ordinati in modo crescente, determinare se l'intero k è presente in a.

Es. array a: [1,3,9,17,34,95,96], intero k: 50.

Soluzione: consideriamo il seguente funzione che realizza l'algoritmo di ricerca sequenziale:

public static boolean ricercaSequenziale(int[] a, int k) {
   for (int i = 0; i < a.length; i++)
      if (a[i]==k) return true;
   return false;
}

La funzione ricercaSequenziale realizza un algoritmo corretto per risolvere il problema (nota, esso in realtà non sfrutta l'ordinamento dell'array).

Ma quanto costa la sua computazione? Esistono funzioni/algoritmi più efficienti?

Il costo computazionale di una funzione/programma è un costo definito in termini di risorse di calcolo.

Le risorse di calcolo fondamentali sono due:

1. quantità di tempo necessario alla computazione (tempo)
2. quantità di memoria utilizzata (spazio)

Esistono altre risorse di calcolo che possono essere rilevanti in casi particolari (non trattate in questo corso), ad esempio

• la quantità di traffico generata su una rete di calcolatori;
• la quantità di dati che devono essere trasferiti da e su disco.

A che serve stabilire il costo computazionale di una funzione/programma/algoritmo?
A confrontare diverse funzioni/programmi/algoritmi che risolvono lo stesso problema, in modo da scegliere il più efficiente.

Concentriamoci sul tempo di calcolo.

La prima risposta che viene in mente è facciamo una prova: scegliamo una particolare configurazione dei dati in ingresso ed eseguiamo il programma misurando il tempo.

Es. Configurazione dei dati in ingresso (input): array a: [1,3,9,17,34,95,96], intero k: 50. Risultato calcolato(output): false. Tempo cronometrato: 10 µsec.

Che cosa sappiamo dopo questo esperimento? Quasi niente!!!

Conosciamo un numero corrispondente ad un dato input. Da cosa è influenzato questo numero?

• macchina utilizzata (hardware usato, sistema operativo, carico sul sistema, qualità del compilatore, linguaggio di programmazione utilizzato, ecc.)
• configurazione dei dati in ingresso (es. se nel nostro esempio il valore cercato k è 1, il tempo è molto minore che se k è 50.
• dimensione dell'input (dimensione del vettore, maggiore è tale dimensione, maggiore è il tempo necessario alla ricerca).

Questa misura non è soddisfacente per capire il costo computazionale insito dell'algoritmo che la nostra funzione realizza (approssimato). Noi vogliamo conoscere questo costo in modo (necessariamente) approssimato:

• indipendentemente dalla particolare macchina utilizzata
• indipendentemente dalla configurazione di ingresso
• al variare della dimensione dell'input

Una misura del costo computazionale soddisfacente deve:

1. basarsi su un modello di calcolo astratto, indipendente dalla particolare macchina
2. svincolarsi dalla configurazione dei dati in ingresso, ad esempio basandosi sulle configurazioni più sfavorevoli (caso peggiore), così da garantire che le prestazioni nei casi reali saranno al più costose quanto il caso analizzato
3. essere una funzione (non un numero!!!) della dimensione dell'input
(la configurazione l'abbiamo fattorizzata via considerando il caso peggiore)
4. essere asintotica, cioè fornire una idea dell'andamento del costo all'aumentare della dimensione dell'input (si noti che essere troppo precisi non avrebbe senso visto che non consideriamo la macchina effettiva che esegue il calcolo).

Cioè siamo interessati al costo (o complessità) asintotico nel caso peggiore.

Esempio

Ad esempio diremo che ricercaSequenziale ha un costo lineare, cioè il costo è una funzione che varia come

a n + b

dove n e' la dimensione dell'array (dim. dell'input) e a e b sono due fattori costanti indipendenti dalla dim. dell'input.

Vedremo che ricercaBinaria ha un costo logaritmico, cioè il costo e' una funzione che varia come

a log(n) + b

dove n è la dimensione dell'array (dim. dell'input) e a e b sono due fattori costanti indipendenti dalla dim. dell'input.

Ne segue che ricercaBinaria e' un algoritmo migliore (piu' efficiente) di ricercaSequenziale.

Ci concentriamo sul costo in tempo.

Idea fondamentale del modello astratto di macchina proposto: ogni istruzione atomica ha costo unitario.

1. istruzione atomica costo unitario. 
   
2. condizione atomica costo unitario.
   
3. istruzione condizionale.

   if (<condizione>)
      <parte if> 
   else
      <parte else>

   costo dell'istruzione if-else è: c₁ + c_if se la condizione è vera e c₁ + c_else se la condizione è falsa,
   dove c₁  è il costo della condizione, c_if il costo della parte if e c_else il costo della parte else
   

4. istruzione di ciclo (consideriamo l'istruzione while, le altre istruzioni di ciclo, come il for, si possono ridurre a questa):

   while (<condizione>)
      <corpo del ciclo>

   costo dell'istruzione while è: SUM_{i = 1..n_rip}(c_i+d_i)

   dove:

   • n_rip è il numero di volte che viene eseguito il ciclo
   • c_i è il costo della i-esima iterazione della condizione
   • d_i è il costo della i-esima iterazione della corpo del ciclo
5. blocco

   { 
     <ist_1>
     ...
     <ist_n>
   }

   costo dell'istruzione blocco e': c₁+ ... + c_n

6. invocazione di una funzione (metodo)
   costo pari al costo dell'esecuzione del corpo della funzione. Nota: costo allocazione record di attivazione pari a 0 (ma attenzione che il costo in spazio e' pari alla dimensione del record di attivazione).
7. istruzione e condizione con chiamata di funzione
   costo pari alla somma dei costi delle funzioni invocate + 1

Nota: stiamo assumendo che

v[i]==10

e

v[i]==10*10*10*10/4*10*10*10/3*10*10/2*10*10/10*10

abbiano entrambe costo 1, nonostante la seconda sia sicuramente piu' costosa delle prima.
Il punto e' che il suo costo non dipende dalla dimensione dell'input!!!

Esempio

public static boolean ricercaSequenziale(int[] a, int k) {
   for (int i = 0; i < a.length; i++)
      if (a[i]==k) return true;
   return false;
}

Es1 input a: [1,3,9,17,34,95,96], k:9

Costo:

• 1 (inizializzazione int i = 0;)
• 3 (confronti i < a.length)
• 3 (confronti a[i] == k)
• 2 (istruzioni i++;)
• 1 (istruzione return true;)
• totale 10

Es2 input a:[1,3,9,17,13,95,96], k:50

Costo:

• 1 (inizializzazione int i = 0;)
• 8 (confronti i < a.length)
• 7 (confronti a[i] == k)
• 7 (istruzioni i++;)
• 1 (istruzione return false;)
• totale 24

Caso peggiore

Il passo successivo e' liberarsi della particolare configurazione dei dati in ingresso.

Quale e' il caso peggiore per ricercaSequenziale?

L'elemento cercato k non occorre nell'array a.

Costo per un array di dimensione n (dimensione dell'input):

• 1 (inizializzazione int i = 0;)
• n+1 (confronti i < a.length)
• n (confronti a[i] == k)
• n (istruzioni i++;)
• 1 (istruzione return true;)
• totale 3 n + 3

Nota 3 n + 3 è una funzione (non un semplice numero) ed n, cioè la dimensione dell'array, è la dimensione dell'input!
La ricerca sequenziale ha un costo lineare.

Alternative al caso peggiore

Caso peggiore

Il caso peggiore corrisponde a considerare la configurazione dell'input piu' sfavorevole per il programma/algoritmo - molto significativo

Caso migliore

Il caso migliore corrisponde a considerare la configurazione dell'input piu' favorevole per il programma/algoritmo - poco significativo (nel caso di ricercaSequenziale dice che il costo e' costante!)

Caso medio

Il caso medio corrisponde a considerare la "media" tra le configurazioni dell'input possibili - abbastanza significativo

Caso medio (cenni)

Vogliamo considerare il costo nei casi reali o comuni.

Idea: uso teoria delle probabilità

• fisso una distribuzione per le configurazioni dell'input
• calcolo costo medio

Esempio: Consideriamo ricercaSequenziale

assumiamo che k appartenga effettivamente al vettore, e consideriamo una distribuzione uniforme, tutte le configurazioni dell'input equiprobabili.

In altre parole, k si trova in posizione i-esima (1 <= i <= n) con probabilità 1/n, dove n e' la dimensione dell'array.

Costo nel caso k si trovi in posizione i-esima:

• 1 (inizializzazione int i = 0;)
• i (confronti i < a.length)
• i (confronti a[i] == k)
• i-1 (istruzioni i++;)
• 1 (istruzione return true;)
• totale 3 i+ 1

Ora calcoliamo la media:

SUM _i=1..n 1/n (3 i + 1)   =   1/n (3 (SUM _i=1..n i) + n), si ricorda che SUM _i=1..n i = ((n+1) n) / 2, quindi abbiamo 3/2(((n+1) n)/n) + n/n = (3n + 5)/2, cioè ancora costo lineare.

Nota: quale è il problema di questo tipo di analisi?

La scelta della distribuzione!!! In generale è molto difficile scegliere la distribuzione in modo da rispecchiare i "casi reali"!

Dimensione dell'input

Il costo di un programma/algoritmo e' una funzione dell'input.

Esempio: Il costo (nel caso peggiore) di ricercaSequenziale e' 3n+3, dove n, la dimensione dell'array (cioè il num. dei suoi elementi), è il parametro che caratterizza la dimensione dell'input.

La scelta del parametro che caratterizza la dimensione dell'input e' spesso semplice:

• Es ricercaSequenziale su in array: dimensione dell'input e' la dimensione dell'array
• Es. ricerca su un albero binario: dimensione dell'input e' il numero di nodi dell'albero
• Es ricerca su una collezione: dimensione dell'input e' il numero di elementi della collezione

Tuttavia ci sono casi più complessi:

Esempio

public static int fattoriale(int n) {
   int fatt = 1;
   int i = 1;
   while (i<=n) {
      fatt = fatt*i;
      i++;
   }
   return fatt;
}

Costo:

• 1 (inizializzazione int fatt = 1;)
• 1 (inizializzazione int i = 1;)
• n+1 (confronti i <= n)
• n (istruzioni fatt = fatt * i;)
• n (istruzioni i++;)
• 1 (istruzione return fatt;)
• totale 3 n+ 4

Cioè il calcolo del fattoriale è lineare?

Attenzione quale è il parametro che caratterizza la dimensione dell'input?

1. il valore n: allora il costo rispetto alla dimensione dell'input n è 3n+4, cioè costo lineare.
2. il numero di cifre d utilizzato per rappresentare n : d è circa uguale log₁₀(n), quindi n = 10^d, ed il costo rispetto alla dimensione d dell'input e' 3 10^d + 4, cioè costo esponenziale!

Nota: abbiamo assunto che fatt = fatt*i; costi 1, ma in realta' essa dipende dall'input! (il fattoriale cresce ad ogni iterazione e quindi cresce il costo dell' istruzione). Per tenere conto di questo potremo adottare una macchina astratta piu' sofisticata che associa alle istruzioni/condizioni atomiche costi logaritmici. Tuttavia, tranne in casi particolari (vedi corso di Algoritmi e Strutture Dati) questa analisi piu' sofisticata non e' necessaria.

Per farlo possiamo usare il seguente programma:

   public static void main(String[] args) {
      int n=5;
      for (int riga =1; riga<=n; riga++) {   
          for (int col =1; col<=n; col++) 
              System.out.print(riga%col+" ");
          System.out.println();
      }
   }

Determinarne il costo.

 Esercizio 2 Si consideri la funzione:

   public static int somma(int m, int n) { // m, n >= 0
      while (n > 0) {
	     m = m+1;
         n = n-1;
      }
      return m;
   }

Determinarne il costo. (Suggerimento si chiarisca inizialmente quale parametro caratterizza la dimensione dell'input.)

Studio del comportamento asintotico

Idea: trascurare costanti moltiplicative e termini di ordine inferiore.

• Fornisce una idea precisa del costo all'aumentare della dimensione dell'input.
  
• Rende l'analisi del costo insensibile rispetto alle approssimazioni introdotte nel modello di costo adottato.
  
• Consente di semplificare i calcoli.

Esempio:

• a n + b ==> lineare
• a n² + b n + c==> quadratico
• a log_b n + c==> logaritmico

Come fare formalmente?
Come nel calcolo infinitesimale!

Notazione O (O-grande)

1. Da un certo punto n₀ in poi, la dimensione di f (n) non supera quella di g(n) dato un certo fattore di scala c. 
   
2. Se f (n) è O(g(n)),  f (n) è anche O(10  g(n)) e anche O(5 + g(n)).

Considerando O-grande siamo interessati all'andamento asintotico della funzione di costo del programma.

Osservazioni sulla notazione O

• Per determinare O di un polinomio basta considerare il coefficiente di grado maggiore

  4 n² + 16 n + 18    è    O(n²)
  5n⁵ + 4n³ + n + 10   è    O(n⁵)

• 3n è O(n) ma anche O(n²)! Attenzione però: si sceglie sempre l'approssimazione migliore possibile!!! Cioè O(n)!
  
• La base dei logaritmi non conta: log₁₀(n)   =   log₁₀(2)  log₂(n)  =  k log₂(n) tipicamente si scrive O(log(n)) tralasciando la base (intesa come base 2).
  
• n + log(n) < n + n (da un certo n₀ in poi) = 2n ==> O(n)
  
• n log (n) < n² quindi è O(n²), ma per essere più precisi è O(n log(n)).
  

Costo di un programma/algoritmo

Definizione: Un algoritmo A ha costo (o complessità) O(g(n)) se la quantità di tempo (spazio) sufficiente per eseguire A su un input di dimensione n nel caso peggiore è O(g(n)) .

Funzioni di costo

O(1) funzione di costo costante (che non dipende dai dati in ingresso). 

O(n) funzione di costo lineare

O(log(n)) funzione di costo logaritmica

O(n log(n)) funzione di costo n log n (a volte detta "quasi-lineare")

O(n^k) funzione di costo  polinomiale cioè limitata da un polinomio di grado k (cioè, a_kn^k + a_{k - 1}n^{k - 1} +...+ a₁n + a₀, o più semplicemente a_kn^k ) dove k è una costante.

O(kⁿ) funzione di costo esponenziale cioè limitata da una funzione esponenziale kⁿ, con k una costante maggiore di 1

...

Funzioni di costo (valori)

Valutazione semplificata del costo: scomposizione dei costi

• Costo programmi sequenziali
  Si consideri il programma A;B; in cui il costo di A; è O(f_A(n)) e il costo di B; è O(f_B(n)). Il costo di A;B; è O(max(f_A(n), f_B(n)).
  
• Passo più costoso
  Si consideri il programma A;B; in cui il costo di A; è O(f_A(n)) e il costo di B; è O(f_B(n)), con f_A(n) = O(f_B(n)). Il costo di A;B; è O(f_B(n)).
  
• Costo programmi con sottoprogrammi ripetuti
  Sia A un programma che richiede l'esecuzione ripetuta di un insieme di istruzioni. Sia f_i(n) il costo della i-esima ripetizione e g(n) il numero di ripetizioni. Il costo di A è O(SUM_(i=1..g(n)) f_i(n)).
  
  Caso particolare: costo di tutte le ripetizioni uguale, allora il costo di A è O(f(n) g(n)).

Valutazione semplificata del costo: operazioni dominanti

• Sia A un programma con costo O(f_A(n)), una operazione si dice dominante se, nel caso peggiore, viene ripetuta un numero di volte g(n) = O(f_A(n)).

• Se una programma A ha una operazione dominante che viene eseguita un numero di volte O(g(n)), allora il costo del programma è O(g(n)).

• Tipicamente per individuare le operazioni dominanti basta esaminare le istruzioni e i confronti eseguiti nei cicli più interni dei programmi, oppure eseguiti nell'ambito delle attivazioni ricorsive.

Ricerca binaria

 Sia a un vettore di n elementi stringa a₀,..., a_{n - 1} ordinati in modo crescente ed k l'intero cercato in a.

left l'indice del primo elemento di a 
right l'indice dell'ultimo elemento di a
med l'indice dell'elemento centrale pari ad (left + right)/2.

1. Se a(med) = k allora abbiamo trovato l'elemento e ritorna true
2. Se a(med) < k allora cerchiamo k nella metà destra del vettore, ponendo left = med
3. se a(med) > k allora cerchiamo k nella metà sinistra del vettore ponendo right = med 

Ricerca binaria: implementazione

/* verifica se il valore k e' contenuto all'interno del 
array a ordinato */

public static boolean ricercaBinaria(int[] a, int k) {
   int left = 0, right = a.length-1;
   while (left<=right) {
      int med = (left+right)/2;
      if (a[med]==k)
         return true;
      else if (a[med]<k)
         left = med+1;
      else // a[med]>k
         right = med-1;
   }
   return false;
}

Ricerca binaria: costo 

Esiste una operazione dominante? Quale?
Tutte le operazioni all'interno del ciclo while: es. condizione (left <= right) oppure istruzione med = (left+right)/2, ecc.

Quante volte viene eseguito il ciclo while nel caso peggiore?
Ad ogni iterazione vengono scartati metà degli elementi dell'array.

Quindi quanti elementi devono essere ancora analizzati ad ogni iterazione?
Vediamo: iter 0, n elem; iter 1, n/2 elem; iter 2, n/4 elem; iter 3, n/8;... iter n/2ⁱ...

Quante volte posso iterare?
Fino a quando n/2ⁱ >= 1. Cioè 2ⁱ <=n; cioè i <= log₂(n). Il numero di iterazioni è al massimo pari a  log(n).

Quindi considerando che il costo di ciascuna iterazione è costante, facendo riferimento al costo dei sottoprogrammi ripetuti,abbiamo che il costo di ricercaBinaria è O(log(n)).

Esempio: Sia l'array a = [3, 5, 7 ,11, 17 ,19, 23, 31] e l'elemento k cercato 6.
Il costo della ricerca è log₂(8) = 3. 

Esercizio 4 Si consideri la funzione

public static void stampaRigheMatrice(short[][] A) {
  for (int i=0; i<A.length; i++) {    // scandisce righe
    for (int j=0; j<A[0].length; j++) // scandisce elementi riga i
      System.out.print(A[i][j]+" ");  // stampa elemento riga
    System.out.println();             // fine riga
   }
}

Esercizio 5 Si consideri il seguente metodo che prende come parametri due matrici A e B entrambe di dimensione n x n e restituisce una nuova matrice ottenuta sommando gli elementi corrispondenti di A e B.

public static double[][] sommaMatrici(double[][] A, double[][] B) {
  double[][] C = new double [A.length][A[0].length];
  for (int i=0; i<A.length; i++)
    for (int j=0; j<A[0].length; j++)
      C[i][j] = A[i][j] + B[i][j];
  return C;
}

Esercizio 6 Si consideri il seguente metodo che prende come parametri due matrici A e B entrambe di dimensione n x n e restituisce una nuova matrice ottenuta come prodotto di A e B.

public static double[][] prodottoMatrici(double[][] A, double[][] B) {
  double[][] C = new double [A.length][A[0].length];
  for (int i=0; i<A.length; i++)
    for (int j=0; j<A[0].length; j++) {
      C[i][j]=0;
      for (int k=0; k<A[0].length; k++)
        C[i][j] += A[i][k] * B[k][j];
    }
  return C;
}

Esercizio 7 Si determini il costo di tutti i metodi della classe TestoCriptato

public class TestoCriptato {
  // rappresentazione degli oggetti della classe
  private int chiave;
  private String testo;

  // costruttori
  public TestoCriptato(String testoNonCriptato) {
    chiave = 0;
    testo = testoNonCriptato;
  }
  public TestoCriptato(String testoNonCriptato, int chiave) {
    this.chiave = chiave;
    testo = codifica(testoNonCriptato,chiave);
  }

  // altri metodi pubblici
  public String getTestoCriptato() {
    return testo;
  }
  
  public String getTestoDecriptato(int chiave) {
    if (chiave == this.chiave)
      return decodifica(testo, chiave);
    else return null;
  }
  
  public boolean estChiave(int chiaveCandidata) {
    return chiaveCandidata == chiave;
  }
  
  public void setChiave(int chiave, int nuovaChiave) {
    if (chiave == this.chiave) {
      this.chiave = nuovaChiave;
      testo = codifica(decodifica(testo,chiave),nuovaChiave);
    }
  }

  // metodi ausiliari
  private static String codifica(String testo, int chiave) {
    String testoRis;
    char c;
    int ci;
    testoRis = "";
    for (int i = 0; i < testo.length(); i++) {
      c = testo.charAt(i);
      ci = (int)c;
      ci = ci + chiave;
          c = (char)ci;
      testoRis = testoRis + String.valueOf(c);
    }
    return testoRis;
  }
  
  private static String decodifica(String testo, int chiave) {
    String testoRis;
    char c;
    int ci;
    testoRis = "";
    for (int i = 0; i < testo.length(); i++) {
      c = testo.charAt(i);
      ci = (int)c;
      ci = ci - chiave;
      c = (char)ci;
      testoRis = testoRis + String.valueOf(c);
    }
    return testoRis;
  }
}

Esercizio 8 Scrivere un metodo static int numeroDuplicati(int[] A) che restituisce il numero di duplicati nell'array A, ovvero il numero di valori distinti che compaiono più volte come elementi dell'array. 

Determinare il costo del metodo.

Costo rispetto allo spazio

Fino ad adesso abbiamo focalizzato l'attenzione principalmente sul costo rispetto al tempo. Cosa cambia quando consideriamo invece lo spazio?

La definizione di O-grande e di delimitazione superiore di costo di un programma/algoritmo date precedentemente naturalmente sono ancora valide se invece di considerare quantità di tempo consideriamo quantità di spazio.

Modello di costo per lo spazio: mentre la quantità di tempo è calcolata considerando istruzioni/condizioni atomiche con costo unitario, quando passiamo allo spazio consideriamo unitario la quantità di memoria necessaria per memorizzare una variabile di qualsiasi tipo, incluse naturalmente quelle allocate nei record di attivazione delle funzioni.

Due considerazioni importanti:

1. Il costo rispetto allo spazio dovrebbe essere sempre minore o uguale al costo rispetto al tempo
   • utilizzare spazio in memoria implica utilizzare tempo per scrivere su questo spazio
   • lo spazio può essere riutilizzato, mentre il tempo no
2. Non consideriamo lo spazio necessario per rappresentare l'input, ma solo lo spazio di lavoro aggiuntivo (incluso l'output). Si dà per scontato che l'input vada rappresentato!

Costo rispetto allo spazio

Esempio:

public static boolean ricercaSequenziale(int[] a, int k) {
   for (int i = 0; i < a.length; i++)
      if (a[i]==k) return true;
   return false;
}

Costo in tempo O(n).
Costo in spazio?
O(1)! Spazio costante! perchè?

Esempio (implementazione ricorsiva di ricerca sequenziale):

public static boolean ricercaSequenzialeR(int[] a, int k, int i) {  // i denota la pos iniziale del vettore

   if (i >= a.length) return false;
   else if (a[i]==k) return true;
   else return ricercaSequenzialeR(a,k,i+1);
}

• Costo in tempo?
  
  O(n).
  
  
• Costo in spazio?
  
  O(n)! perchè? Dipende dal numero di record di attivazione che devono essere contemporanemente pressenti in memoria.

In realtà, alcuni compilatori sono in grado di riconoscere che questo è un tipo di ricorsione molto semplice (la funzione che invoca se stessa ricorsivamente non usa i risultati i tale invocazione), detta "tail recursion", e in presenza di tale tipo di ricorsione non allocano un nuovo record di attivazione, ma riusano il record di attivazione del chiamante.

Costo rispetto allo spazio

Esempio:

public static boolean ricercaBinaria(int[] a, int k) {
   int left = 0, right = a.length-1;
   while (left<=right) {
      int med = (left+right)/2;
      if (a[med]==k)
         return true;
      else if (a[med]<k)
         left = med+1;
      else // a[med]>k
         right = med-1;
   }
   return false;
}

Costo in tempo O(log(n)).
Costo in spazio?
O(1)! Spazio costante! perchè?

Esempio (implementazione ricorsiva di ricerca binaria):

public static boolean ricercaBinariaR(int[] a, int k, int left, int right) {
   if (left > right) return false;
   else { 
      int med = (left+right)/2;
      if (a[med]==k)
         return true;
      else if (a[med]<k)
         return ricercaBinariaR(a,k,med+1,right);
      else  // a[med]>k
         return ricercaBinariaR(a,k,left,med-1);
   }
}

Costo in tempo O(log(n)).
Costo in spazio?
O(log(n))! perchè?