Complessità: asintotica

di

Dopo aver analizzato la complessità in tempo di alcuni algoritmi possiamo osservare che

  1. il caso ottimo di un algoritmo è quasi sempre costante
  2. e non sarebbe significativo per la bassa probabilità che si presenti
  3. il caso pessimo e il caso medio dipendono dalla dimensione dei dati
  4. è difficile calcolare con precisione le costanti moltiplicative
  5. per n piccolo è difficile decidere tra due algoritmi
  6. mentre per n abbastanza grande la differenza di comportamento diventa evidente

Per dare una misura della complessità in tempo di un algoritmo si preferisce

  • dare una misura approssimata del calcolo del tempo di esecuzione T(n)
  • studiare il caso pessimo oppure il caso medio
  • valutare il comportamento per n sufficientemente grande…

Definizione

Si introduce la complessità asintotica e la notazione O(f(n))

una funzione g(n) è O(f(n)), e si legge g(n) è dell’ordine o grande di f(n), se esistono una costante moltiplicativa c ed un numero naturale n0 tali che g(n) ≤ c f(n), per una certa c e per ogni n ≥ n0

Esempio

Data la funzione g(n)=2n2+4n+2, scegliendo opportunamente i valori c=2.1 e n0 ≥ 41 si ha

g(41) = 3528 < 3530.1 = 2.1(41)2 = c n02

allora

g(n) < 2.1 n2, per n ≥ 41

e quindi

g(n) ∈ O(n2)

In pratica

  • le costanti moltiplicative diventano trascurabili
  • le combinazioni lineari di funzioni diventano trascurabili
  • è sufficiente individuare la funzione più pesante
  • tutte le funzioni lineari sono dell’ordine O(n)
  • tutte le funzioni quadratiche sono dell’ordine O(n2)
  • …

La complessità in tempo viene riassunta in una funzione più significativa che rappresenta la complessità in tempo asintotica.

Esempi

Le costanti sono spropositate per evidenziare l’aspetto asintotico… della complessità

  • T1(n)=2n+400log2n ∈ O(n)
  • T2(n)=2n3+400n ∈ O(n3)
  • T3(n)=20.000+log10n ∈ O(logn)
  • T4(n)=3n+400n4+100.000.000 ∈ O(2n)

Tabella

Le funzioni di complessità interessanti in ambito informatico sono relativamente poche

  • O(1), costante
  • O(log n), logaritmica
  • O(n), lineare
  • O(n log n), enne-log-enne
  • O(n2), quadratica
  • O(nk), polinomiale
  • O(2n), esponenziale