Complessità in tempo asintotica

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito

Complessità in tempo asintotica

Osservazioni

	il caso ottimo di un algoritmo è quasi sempre costante (e comunque non sarebbe significativo…) mentre quello pessimo/medio dipende dalla dimensione dei dati
	è difficile calcolare con precisione le costanti moltiplicative
	per n piccolo è difficile decidere tra due algoritmi mentre per n abbastanza grande…

Si preferisce dare una misura della complessità in tempo di un algoritmo dando

	la misura approssimata del calcolo del tempo di esecuzione T(n)
	studiando il suo comportamento per n sufficientemente grande in modo che la discussione sia "significativa"...

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

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

Esempio

g(n)=2n²+4n+2 ≤ c*f(n)=cn², con c=2.1 e n≥41 (3528, 3530.1)

allora

g(n)=2n²+4n+2 ε O(n²)

In pratica le costanti moltiplicative diventano trascurabili e così le combinazioni lineari di funzioni.

Tutte le funzioni lineari sono dell'ordine o-grande di n, tutte le funzioni quadratiche sono dell'ordine o-grande di n², ...

La complessità in tempo viene "riassunta" in una funzione più "significativa", complessità in tempo asintotica.

Esempi

T₁=2n+400log₂n ε O(n)

T₂=2n³+400n ε O(n³)

T₃=20000+log₁₀n ε O(log n)

T₄=3ⁿ+400n⁴+100000000 ε O(2ⁿ)

Nella pratica della programmazione compaiono i seguenti casi interessanti (in ordine crescente di complessità)

T(n) complessità in tempo	O() complessità asintotica		algoritmo	N.B.
c	Costante	O(1)		**
c*log_an+...	Logaritmica	O(logn)	Ricerca binaria	*
c*n+...	Lineare	O(n)	Ricerca sequenziale
c*nlog_an+...	"enne-log-enne"	O(nlogn)	Ordinamenti evoluti	*
.	.	O(n^1.2)	Shell sort
c*n²+...	Quadratica	O(n²)	Ordinamenti ingenui
c*n³+...	Cubica	O(n³)	Prodotto di matrici	***
c*n^p+...	Polinomiale	O(n^p)
c*aⁿ+...	Esponenziale	O(2ⁿ)	Torre di Hanoi	*

Note

	..., qualsiasi combinazione lineare delle funzioni delle righe precedenti
	*, con a > 1
	**, qualsiasi tempo, anche grande, che non dipende da n
	***, esistono algoritmi migliori per lo stesso problema

Complessità in tempo asintotica - ApPuNtIdIuNiNfOrMaTiCo

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito