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. non sarebbe significativo per la bassa probabilità che ha di presentarsi
  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. 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) \ \le \ c\cdot f(n) per una certa c e per ogni n \ \gt \ n_0

Esempio

Data la funzione g(n)=2 n^2+4 n+2, scegliendo opportunamente i valori c=3 e n_0 \ \gt \ 5 si ha

g(5) = 72 < 75 = 3(5)2 = c·f(n0)

allora g(n) \ \le \ c\cdot f(n) per n ≥ 5 e quindi g(n) \in O(n^2)

In pratica

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

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à

  • T_1(n)=2\cdot n +400\cdot \log_2 n \ \lt \ 3\cdot n \in O(n)
  • T_2(n)=2\cdot n^3 +400\cdot n \ \lt \ 3\cdot n^3 \in O(n^3)
  • T_3(n)=20000+\log_{10}n \ \lt \ \log n \in O(\log n)
  • T_4(n)=3^n + 400\cdot n^4+1000000 \ \lt \ 2\cdot 3^n \in O(3^n)

Elenco

Per tutte le semplificazioni che abbiamo adottato le funzioni di complessità veramente interessanti in ambito informatico sono poche

  • O(1), costante
  • O(\log n)logaritmica
  • O(n)lineare
  • O(n \log n), enne-log-enne
  • O(n^2), quadratica
    • O(n^3), cubica
    • O(n^k), polinomiale
  • O(2^n), esponenziale
    • O(3^n), …
    • O(n!), più che esponenziali
    • O(n^n), …