Complessità: asintotica

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
Notice: This work is licensed under a BY-NC-SA. Permalink: Complessità: asintotica

Comments are closed.