Come valutare la complessità di un algoritmo o…

Per valutare la complessità di un algoritmo, si utilizza l'analisi asintotica, che permette di descrivere l'efficienza dell'algoritmo in funzione della dimensione dei dati di input ($n$). I passaggi principali:

Definizione delle operazioni di base: Si identificano le operazioni il cui tempo di esecuzione dipende significativamente da $n$ (ad esempio, confronti, assegnazioni, operazioni aritmetiche).
Calcolo del numero di operazioni: Si determina la quantità di operazioni di base in funzione di $n$. Questo può essere una formula precisa o una stima.
Determinazione della classe asintotica: Si usano le notazioni Grande O ($O$), Omega ($\Omega$) e Theta ($\Theta$) per descrivere il comportamento asintotico superiore, inferiore e preciso, rispettivamente.
- $O(f(n))$: L'algoritmo viene eseguito in un tempo che non supera una costante moltiplicata per $f(n)$ per grandi $n$. È usato per descrivere il caso peggiore.
- $\Omega(f(n))$: L'algoritmo viene eseguito in un tempo che non è inferiore a una costante moltiplicata per $f(n)$ per grandi $n$. È usato per descrivere il caso migliore.
- $\Theta(f(n))$: L'algoritmo viene eseguito in un tempo proporzionale a $f(n)$ per grandi $n$. È usato per descrivere il caso medio o quando il migliore e il peggiore hanno lo stesso ordine asintotico.

L'uso più comune è la Grande O ($O$) per descrivere il limite superiore del tempo di esecuzione, importante per comprendere la scalabilità dell'algoritmo nel peggior scenario.

Omissione di costanti e termini minori: Quando si determina la notazione asintotica, si ignorano i fattori costanti e i termini di ordine inferiore, poiché per grandi $n$ domina la funzione con il più grande esponente. Ad esempio, per $3n^2 + 5n + 10$, la notazione asintotica sarà $O(n^2)$.

Classi asintotiche tipiche (in ordine di crescente complessità):

$O(1)$: Complessità costante (il tempo di esecuzione non dipende da $n$).
$O(\log n)$: Complessità logaritmica (il tempo di esecuzione cresce molto lentamente con $n$, caratteristico degli algoritmi di ricerca binaria).
$O(n)$: Complessità lineare (il tempo di esecuzione è proporzionale a $n$, caratteristico delle ricerche lineari semplici).
$O(n \log n)$: Complessità lineare-logaritmica (tipico di algoritmi di ordinamento efficienti come Quick Sort o Merge Sort).
$O(n^2)$: Complessità quadratica (il tempo di esecuzione cresce con il quadrato di $n$, caratteristico di algoritmi di ordinamento semplici come Bubble Sort).
$O(n^c)$ (per $c > 1$): Complessità polinomiale.
$O(c^n)$ (per $c > 1$): Complessità esponenziale (il tempo di esecuzione cresce molto rapidamente con $n$, tipico di ricerche esaustive).
$O(n!)$: Complessità fattoriale (la più alta classe di complessità, cresce estremamente rapidamente).

Per determinare la complessità asintotica di strutture cicliche:

Blocchi di codice sequenziali: Si somma la complessità dei blocchi. $O(A+B) = O(\max(A, B))$.
Cicli annidati: Si moltiplica il numero di iterazioni dei cicli. Un ciclo con $n$ iterazioni, all'interno del quale un altro ciclo con $m$ iterazioni, ha complessità $O(n \times m)$. Se $m=n$, la complessità è $O(n^2)$.
Cicli con riduzione della dimensione dell'input: Ad esempio, dividendo per 2 ad ogni iterazione, si ottiene una complessità logaritmica ($O(\log n)$).

Esempio:

Percorso semplice di un array:

# Ricontare le operazioni di base (confronti, assegnazioni)
# L'operazione principale è il confronto nel ciclo
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 assegnazione (fuori dal ciclo)
    for i in range(1, len(arr)): # Il ciclo viene eseguito $n-1$ volte
        # Dentro il ciclo:
        # 1 confronto (if arr[i] > max_val)
        # potenzialmente 1 assegnazione (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Se la dimensione dell'array è $n = \texttt{len(arr)}$, il ciclo viene eseguito $n-1$ volte. In ogni iterazione, vengono eseguite operazioni costanti. Il numero totale di operazioni è proporzionale a $n$. Complesso asintotico: $O(n)$.

Esempio: Ordinamento per inserimento (Insertion Sort)

# Ricontare le operazioni di base
# Operazioni principali: confronti e assegnazioni/spostamenti di elementi
def insertion_sort(arr):
    # Il ciclo esterno viene eseguito in $n-1$ volte
    for i in range(1, len(arr)):
        key = arr[i] # 1 assegnazione
        j = i - 1 # 1 assegnazione
        # Il ciclo interno nel caso peggiore viene eseguito $i$ volte
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 assegnazione (spostamento)
            j -= 1 # 1 sottrazione e 1 assegnazione
        arr[j + 1] = key # 1 assegnazione

Il ciclo esterno viene eseguito $n-1$ volte. Nel caso peggiore (array in ordine inverso), il ciclo interno si esegue in media $i$ volte (o fino a $i$ volte). La somma delle operazioni in tutte le iterazioni del ciclo esterno è circa $1 + 2 + ... + (n-1) \approx n^2/2$. Complesso asintotico: $O(n^2)$ nel caso peggiore e medio, $O(n)$ nel caso migliore (array già ordinato). Quando si valuta la complessità, si considera generalmente il caso peggiore (Grande $O$).

Come valutare la complessità di un algoritmo o determinarne l'asintoto?