Skip to content

2.04 Lezione 4

Jump to bottom
Giuliano Ranauro edited this page Sep 27, 2021 · 5 revisions

Efficienza degli algoritmi

Nella scorsa lezione ci siamo fermati sull'algoritmo 2-Sum :

int count = 0;
	for(int i = 0; i < N; i++)
    for(int j = i+1; j < N; j++)
      if(a[i] + a[j] == 0)
        count ++;

La domanda è la seguente: è l'algoritmo migliore per questa applicazione?

Ovviamente no, perchè questo algoritmo è di tipo Bruteforce.

Siccome per risolvere il problema dovremo sempre effettuare degli accessi all'array, il nostro algoritmo dipenderà sempre dallo stesso modello di costo. Per avere un algoritmo più efficiente, dobbiamo evitare di verificare tutte le combinazioni lineari. Di conseguenza dobbiamo eliminare il secondo ciclo for, in modo da effettuare una sola iterazione sull'array.

Per eliminare il secondo ciclo for, possiamo utilizzare un'altra struttura dati, come un altro array oppure un set.

Sapendo che per avere somma = 0, due numeri devono essere opposti, come ad esempio 5 e -5. Di conseguenza, all'iterazione i, dobbiamo ricercare un elemento nella seconda struttura che sia pari a -a[i].

Per effettuare questa operazione, ci avvaliamo di un HashSet, oppure più semplicemente di un Set.

Così facendo, abbiamo un notevole miglioramento di performance, ma l'algoritmo occuperà più memoria.

Tilde notation

La notazione tilde stima il tempo di esecuzione, o la memoria, come una funzione della grandezza dell'input N. Come abbiamo detto nella precedente lezione andiamo ad ignorare i termini di ordine inferiore:

Operazione Frequenza tilde notation
dichiarazione variabile N + 2 ~ N
accesso all'array N(N-1) ~ N2

Esempio: 3-Sum

int count = 0;
for(int i = 0; i < N; i++)
  for(int j = 0; j < N; j++)
      for(int k = 0; k < N; k++)
        if(a[i] + a[j] + a[k] == 0)
        	count ++;

Anche in questo caso le combinazioni sono date da:

Stimare una somma discreta

Sostituiamo la somma con un integrale, e calcoliamo:

Ordini di crescita comuni

ordini di crescita.png

Questo insieme di funzioni è sufficiente a descrivere l'ordine di grandezza della maggioranza degli algoritmi.

ordine di crescita nome pezzo di codice esempio
1 costante a = b+ c somma di due numeri
log N logaritmico While(N>1){N = N/2; ...} ricerca binaria
N lineare For(int i = 0 ; i< N; i++){...} ricerca del massimo
N log N linearitmico [codice mergesort] mergesort
N2 quadratico doppio loop for controllo delle coppie
N3 cubico triplo loop for controllo delle triplette
2N esponenziale ricerca combinata controllo dei sottoinsiemi

Binary search

Partiamo dal presupposto che l'array sia già ordinato. L'obbiettivo è quello di trovare l'indice della chiave che vogliamo cercare.

Come funziona?

  1. Confrontare la chiave con l'elemento al centro dell'array
  2. Se troppo grande, andare a sinistra.
  3. Se troppo piccolo, andare a destra
  4. Uguale? Trovato.

demo

Cosa succede se sto cercando un elemento che non è presente nell'array?

Nel momento in cui lo = hi allora vuol dire che sono arrivato alla fine dell'algoritmo, e se la chiave da cercare non è stata trovata, ho un search miss e ritorno -1 .

Codice procedurale

public static int binarySearch(int[] a, int key){
  int lo = 0, hi = a.length-1; 						//lo punta al primo elemento, hi all'ultimo
  while(lo <= hi){
    int mid = lo + (hi - lo) / 2;  				//definiamo l'elemento medio
    if (key < a[mid]) hi = mid - 1;				//se la chiave è minore dell'elemento centrale, cerco a sinistra
    else if (key > a[mid]) lo = mid + 1;	//se la chiave è maggiore dell'elemento centrale, cerco a destra
    else return mid;											//altrimenti la chiave è l'elemento centrale
  }
  return -1;															//se arrivo a questo punto vuol dire che la chiave non è stata trovata.
}

Analisi matematica

Vogliamo dimostrare che la ricerca binaria utilizza al massimo 1 + lg N confronti tra chiavi in un array ordinato di grandezza N.

Definiamo T(N) come i confronti di chiavi in sottoarray ordinato di dimenzione <= N.

Siccome andiamo a dividere l'array ad ogni iterazione, otteniamo un tempo di esecuzione pari a 1 + lg N ~ lg N .

Un algoritmo N2 log N per il 3-Sum

Cerchiamo un modo per rendere più efficiente l'algoritmo 3-Sum, che verifica le triplette che danno come somma = 0.

Algoritmo

  1. Ordinare gli N numeri distinti
  2. per ogni coppia di numeri facciamo una ricerca binaria in cui cerchiamo l'opposto della somma di a[i] + a[j].

Analisi

In questo modo possiamo far scendere l'ordine di crescita dell'algoritmo:

  • N2 con l'insertion sort.
  • N2 log N con la ricerca binaria.

Avrò quindi due accessi agli array (per iterazione), e di conseguenza dovrò confrontare tutte le combinazioni lineari tra a[i] e a[j]. Inoltre, per ogni coppia faccio la ricerca binaria, dato da log N.

N2 * log N = N2 log N

Confrontare gli algoritmi

Se ho un ordine di crescita pari a N2 log N rispetto a N3, guadagnamo molto tempo, sopratutto quando abbiamo un input N molto grande.

N Tempo (secondi)
1000 0.1
2000 0.8
4000 6.4
8000 51.1

ThreeSum.java - algoritmo non ottimizzato

N Tempo (secondi)
1000 0.14
2000 0.18
4000 0.34
8000 0.96
16000 3.67
32000 14.88
64000 59.16

ThreeSumDeluxe.java - algoritmo ottimizzato con ricerca binaria

Teoria degli algoritmi

i tipo di analisi che possiamo fare sono di 3 tipi:

  1. Best case: il best case è determinato dall'input più semplice. esempio: se devo ordinare un array l'input più semplice potrebbe essere dato da un array già ordinato.
  2. Worst case : il worst case è determinato dall'input più difficile. In questo caso, possiamo affermare che l'algoritmo avrà delle prestazioni **al più ** pari a x esempio: nell'insertion sort l'input più difficile è dato da un array ordinato al contrario
  3. **Average case: ** ovvero il costo che ci aspettiamo quando il tipo di input non è ne il migliore ne il peggiore, ma dato in maniera randomica.

Goals

Nella teoria degli algoritmi vogliamo da un lato stabilire quella che è la difficoltà di un problema, dall'altro sviluppare degli algoritmi che siano ottimi per la risoluzione di quel problema.

Approccio

L'approccio utilizzato è quello utilizzato finora, ovvero analizzando i termini di ordine superiore ed utilizzare il modello di costo. Per eliminare la variabile del tipo di input, possiamo adottare il worst case scenario, in modo da avere una valutazione costante.

Termini

  • Upper bound: ovvero le performance che garantiamo per ogni input, ovvero quello che prima abbiamo chiamato worst case.
  • Lower bound: la prova che nessun algoritmo potrà performare meglio.
  • Optimal algorithm: ovvero quando upper bound e lower bound coincidono.

esempio: devo cercare tutti gli zeri in un array di dimensione N.

L'Upper bound in questo caso, cioè l'algoritmo che performerà come peggiore, sarà di N, visto che devo ispezionare tutti gli elementi. In questo caso, anche il Lower bound è pari ad N, avremo quindi un algoritmo ottimale.

Notazioni usate comunemente

Possiamo usare delle notazioni per classificare gli algoritmi.

notazione offre esempio usato per
Big Theta Ordine di crescita asintotico Θ(N2) classificare algoritmi
Big Oh Θ(N2) e più piccoli O(N2) sviluppare upper bounds
Big Omega O(N2) e più grandi Ω(N2) Sviluppare lower bounds

Clone this wiki locally