Summaries

Complessità computazionale

Un aspetto importante che non può essere trascurato nella progettazione di un algoritmo è la caratterizzazione dell'efficienza con la quale l'algoritmo stesso viene eseguito su un elaboratore.

L'efficienza non è da intendersi solo in termini di velocità di esecuzione ma anche in funzione dell'utilizzo delle altre risorse.

Tipi di complessità

Esistono 3 tipi di complessità:

• complessità temporale (modellare il tempo di esecuzione)
• complessità spaziale (modellare lo spazio di occupazione di memoria aggiuntiva, cioè la memoria necessaria oltre all'input dato)
• complessità input/output

Risulta essere necessario quindi definire dei parametri e dei criteri attraverso i quali valutare il nostro algoritmo. Bisogna redigere un modello di costo.

Modello di costo

Con questo modella si pensa alla:

• definizione di dimensione dell'input (numero di operazioni da eseguire)
• definizione di istruzione di costo unitario
• complessità di caso migliore e di caso peggiore

In generale, uno stesso problema può essere risolto in più modi diversi, cioè con algoritmi differenti, i quali a loro volta hanno un grado di efficienza variabili. La caratterizzazione di un algoritmo, in funzione della dimensione dell'input, è data quando n tende all'infinito.

Istruzioni di costo unitario

È una operazione che non dipende dai valori e dai tipi di variabili.

• lettura/scrittura (I/O)
• assegnamento, operazioni aritmetiche predefinite, return
• accesso ad elementi di array (built-on)
• valutazione di una qualsiasi espressione booleana

Queste sono utili per trovare un modo per esprimere quantitativamente il numero di operazioni necessarie per eseguire un algoritmo.

Esempi di calcolo della complessità

i = 1; // assegnamento esterno: 1
while (i <= n) // numero di test: n+1
    i = i + 1; // assegnamento interno n*1

// passi base: 2+2*n (funzione in termini della dimensione dell'input)

Si deve quindi determinare una funzione in termini della dimensione dell'input per rappresentarci la complessità dell'algoritmo.

if(cond) { ... }

if(cond) { ... } else { ... }

Poiché qui la situazione è variabile dobbiamo introdurre un tipo di analisi chiamate caso migliore e caso peggiore.

Quindi ogni qual volta ci si presenta un algoritmo in cui il costo complessivo non dipende solamente dalla dimensione dei dati ma anche dal loro valore, dobbiamo applicare la complessità nel caso migliore e nel caso peggiore.

Complessità asintotica

È un criterio matematico per partizionare gli algoritmi in classi di complessità. Esistono 3 notazioni asintotiche:

• θ - definizione stretta: f(x) cresce esattamente come g(n)
• O - definizione superiore: f(x) cresce al più come g(n)
• Ω - definizione inferiore: f(x) cresce almeno come g(n)

Si dia che una funzione f(n) è di ordine y(n) e si serve:

f(n) = O(y(n))

ed è valida se:

∃ c, n₀ > 0 | ∀ n > n₀ 0 < f(n) < c * g(n)

Significa che vogliamo identificare una funzione y(n) tale per cui, a partire da un punto, n₀ vada a limitare superiormente la nostra funzione di potenza cioè:

dove:

• f(n) ∈ O(1) → f(n) costante
• f(n) ∈ O(log n) → f(n) logaritmica
• f(n) ∈ O(n) → f(n) lineare
• f(n) ∈ O(n log n)
• f(n) ∈ O(n²) → f(n) quadratica
• f(n) ∈ O(2ⁿ) → f(n) esponenziale

Usiamo le notazioni asintotiche per caratterizzare il running time di un algoritmo e lo spazio occupato.

Metodo di calcolo

• istruzioni di costo unitario → 1 → O(1)
• blocco di istruzioni: blocco f1, f2, f3 → max{f1, f2, f3}
• costrutti di controllo del flusso:

  
  if(cond) {
  ...  // Fcond + Ftrue
  } else {
  ...  // Fcond + Ffalse
  }

// CASO MIGLIORE: min // CASO PEGGIORE: max

- *cicli:*
```cpp
while(cond) {
    ...  // Fcond + K * Fcorpo
    // K = numero di iterazioni

    // nell'ipotesi che il corpo rimanga costante
}

Nel caso in cui non fosse costante, bisogna "srotolarlo" e cioè individuare una funzione che vada a determinare il numero di operazioni tenendo conto della variazione del costo del blocco.

• cicli innestabili:

  
  for(int i...) // n cicli
  for(int j...) // n cicli

// n*n -> O(n^2)

- *cicli in sequenza:*
```cpp
for(int i...) // n cicli

for(int j...) // n cicli

// max tra i due blocchi

Ricerca binaria

bool ricercaBinaria(int v[], int x, int in, int fin) {
    if(in >= fin) { // O(1)
        return ((in == fin) && (x == v[in]));
    } else { // O(1)
        int medio = (in + fin) / 2;
        if(v[medio] < x)
            in = medio +1;
        else if(x < v[medio])
            fin = medio -1;
        else
            in = fin = medio;

        return ricercaBinaria(v, x, in, fin);
    }
}

Determina la complessità e quindi il numero di volte che viene richiamata la funzione ricercaBinaria.

Quando n = 1,

n/2ᵏ = 1 ⇒ n = 2ᵏ

e quindi avrà complessità:

log₂ n = k

Quest'ultima è una relazione fondamentale della matematica e cioè il numero di volte k per cui un numero x può essere diviso per 2 affinché x sia uguale a 1 e dato da k·log₂ x