Complessità computazionale

Nella lezione del 5/11 abbiamo introdotto il concetto di complessità computazionale. La complessità è relativa ad un algoritmo, espresso come sequenza di passi concreti (ovvero applicazioni elementari di strumenti noti). La complessità temporale dell'algoritmo è data dal numero di passi concreti necessari, in funzione della dimensione degli input: C(n).

Per confrontare tra loro due algoritmi che risolvono lo stesso problema (i.e., calcolano la stessa funzione matematica), usiamo l'analisi asintotica della complessità, che rispetto al benchmarking ha il vantaggio di rimanere valida al variare dell'input set.

Ricordiamo che, in una analisi asintotica C(n) è dominata dal termine che cresce più rapidamente. Distinguiamo tre casi particolarmente importanti:

• 2ⁿ
• n^a, con a costante
• log n

Asintoticamente, un termine del tipo 2ⁿ ha, indipendentemente dalle costanti, sempre una crescita più veloce di qualunque polinomio in n, e a sua volta un polinomio in n cresce più velocemente di un logaritmo.

Abbiamo inoltre introdotto tre notazioni che caratterizzano le classi di complessità: le notazioni O, Ω e Θ.

Data una funzione a valori non negativi f(n), valgono le seguenti proprietà:

• ∃ c, n₀ : f(n) ≤ cg(n), ∀ n > n₀ ⇒ f(n) ∈ O(g(n))
• ∃ c, n₀ : f(n) ≥ cg(n), ∀ n > n₀ ⇒ f(n) ∈ Ω(g(n))
• f(n) ∈ O(g(n)) ∧ f(n) ∈ Ω(g(n)) ⇒ f(n) ∈ Θ(g(n))

O e Ω stabiliscono dei limiti superiore e inferiore per la complessità di un dato algoritmo. Si noti che questi limiti riguardano la crescita asintotica del costo computazionale al crescere della dimensione dei dati, e non invece i casi medio, ottimo e pessimo, che si determinano a parità di dimensione dei dati.

Una imprecisione mia in un esempio svolto oggi a lezione: nel caso f(n) = n + log n , f(n) ∈ Θ(n). Nel caso f(n) = n - log n , dobbiamo dimostrare che n - log n ≥ cn. Lavorando sulla forma generalizzata:

• a n - b log n ≥ c n

abbiamo

• (a - c) n ≥ b log n

per a > c, questo e' vero per valori grandi di n.