Definizione complessità asintotica nel tempo e nello spazio

Dato un algoritmo (corretto) per la soluzione di un problema, una domanda importante da porci è quanto spazio occuperà durante l'esecuzione e quanto tempo richiederà prima di fornire la risposta. Ovviamente, se per risolvere il nostro problema l'algoritmo impiegasse diversi anni, oppure richiedesse una quantità eccessiva di RAM per poter essere eseguito, allora difficilmente sarà di qualche utilità pratica.

Fortunatamente, gli informatici si sono preoccupati di determinare dei metodi per poter calcolare il tempo e lo spazio richiesti per l'esecuzione degli algoritmi, etichettando questo campo con il nome di complessità computazionale.

Per i nostri scopi, è sufficiente sapere che si possono calcolare delle funzioni dei dati in ingresso, che ci forniscono una stima teorica di quanta sarà la massima occupazione di memoria durante il calcolo (complessità nello spazio), o il massimo tempo impiegato (complessità temporale). Quando si calcolano queste funzioni, si fa riferimento a macchine teoriche, per cui lo spazio e il tempo saranno funzioni proporzionali al vero spazio occupato e al vero tempo di esecuzione su un computer reale. Per poter compiere questi calcoli si operano le seguenti approssimazioni:

• tutte le operazioni semplici (assegnazione, test, somma, moltiplicazione,..) valgono un fattore costante 1
• al termine del computo, le costanti vengono trascurate
• la funzione che si calcola è asintotica, nel senso che viene valutata come
  
  $$f_{asintotica}(dati) = \lim_{dati \longrightarrow \infty} f(dati)$$
  
  

Come abbiamo detto, la complessità computazionale che si calcola (nel tempo e nello spazio), è definita come funzione della dimensione dei dati in ingresso. Per cui, questo tiene conto del fatto che se eseguiamo un algoritmo per la ricerca di una persona all'interno di una rubrica con 10 nomi, oppure con 1000 nomi (i dati in ingresso), il tempo sará differente e funzione del numero di persone.

Ovviamente anche l'ordine dei dati, cambierà gli effettivi tempi di esecuzione, per cui si può calcolare una funzione come tempo medio di esecuizione oppure tempo nel caso peggiore. Di solito il caso peggiore è quello più facile da calcolare ed è il solo che verrà considerato in queste note (in alcuni casi i due valori coincidono).

La notazione che utilizzeremo è la seguente: diciamo che un algoritmo ha una complessità computazionale $O(g(N))$ se la funzione che calcolo per l'algoritmo è $f(N)$ (tempo o spazio calcolati) e si ha che

$$\lim_{N \longrightarrow \infty} \frac{g(N)}{f(N)} = C$$

dove $C$ è una costante positiva. Il che significa che a parte termini costanti la complessità del nostro algoritmo tende, al tendere del numero dei dati all'infinito, alla stessa maniera della funzione $g(N)$. Questo vale sia per l'occupazione spaziale che per la proporzionalità al tempo di esecuzione. Per esempio se il tempo calcolato per l'esecuzione del nostro algoritmo è

$$T(N)=3N^3 + 5N^2 + 20$$

si dice che $T(N)$ è $O(N^3)$, infatti se si calcola il limite

$$\lim_{N \longrightarrow \infty} \frac{N^3}{3N^3 + 5N^2 + 20} = \frac{1}{3}$$