Introduzione alla complessità
Paolo Bison
Fondamenti di Informatica 1 A.A. 2004/05 Universit`a di Padova
Introduzione alla complessit `a, Paolo Bison, A.A. 2004-05, 2004-11-25 – p.1/20
Complessità
analisi degli algoritmi in termini di indici di qualitá
algoritmo “migliore”
indici:
occupazione di memoria
tempo di esecuzione
f (n)
calcolo del valore dell’indice in funzione della dimensione dei dati di ingresso
distribuzione dei dati in ingresso
caso peggiore
caso migliore
caso medio
Introduzione alla complessit `a, Paolo Bison, A.A. 2004-05, 2004-11-25 – p.2/20
valore di un polinomio
dato polinomio
A m x m + A m −1 x m −1 + . . . + A 1 x + A 0
valutarlo in x 0
dimensione n = m-1 numero dei coefficienti A i
valore di un polinomio
algoritmo 1
pol ← A 0 i ← 1 while i ≤ m
pot ← 1 k ← i while k > 0
pot ← pot × x 0 k ← k - 1 pol ← A i × pot + pol i ← i+1
¯¯¯|C 0
|
¯¯¯|
| C 1 (n − 1)
|
¯¯¯|
| C 2 P n
l =1 l = C 2 n(n−1) 2
|
¯¯¯| C 3 (n − 1)
|
tempo di esecuzione
f T ‘ (n) = C 0 + C 1 (n − 1) + C 2 n(n − 1)
2 + C 3 (n − 1)
valore di un polinomio
algoritmo 2 regola di Horner
(. . . (A m x + A m −1 )x + A m −2 )x . . . + A 1 )x + A 0 pol ← A m
i ← m-1 while i ≥ 0 do
pol ← pol × x 0 +A i i ← i-1
¯¯¯|D 0
|
¯¯¯|
| D 1 (n − 1)
|
tempo di esecuzione
f T ” (n) = D 0 + D 1 (n − 1)
algoritmo “migliore” ?
comportamento asintotico per n→ ∞
Introduzione alla complessit `a, Paolo Bison, A.A. 2004-05, 2004-11-25 – p.5/20
notazione O
f (n) è O(g(n))
se esistono due costanti positive c e n 0 tali che 0 ≤ f(n) ≤ cg(n)
per ogni n ≥ n 0
n
0c g(n)
n f(n)
g(n) è un limite asintotico superiore per f(n)
limite superiore di f(n) a meno di un fattore costante
limite superiore alla complessità dell’algoritmo
Introduzione alla complessit `a, Paolo Bison, A.A. 2004-05, 2004-11-25 – p.6/20
classi di complessità k costante log n logaritmica
√ n
n lineare
n log n subquadratica n 2 quadratica n 3 cubica n a polinomiale a n esponenziale
n! fattoriale
10 20 30 40 50 60
10 20 30 40 50 60
log(x)2 sqrt(x) x**2x 2**x
valore di un polinomio f ‘ (n) = O(n 2 ) f ” = O(n)
caveat
f (n) equivalenti a meno di un fattore costante
0 500 1000 1500 2000
0 2 4 6 8 10
1000*x 10*x
valori di n sufficientemente grandi
per valori piccoli di n un algoritmo di complessità maggiore potrebbe essere più efficiente
differenti complessità nei casi migliore, peggiore e
medio
Radice intera
calcolo della radice quadrata intera di un numero n > 0
la radice intera è quel numero m che soddisfa le condizioni m 2 ≤ n e (m + 1) 2 > n
Introduzione alla complessit `a, Paolo Bison, A.A. 2004-05, 2004-11-25 – p.9/20
Radice intera - I
metodo
static public int isqrtI(int n) {
int i,m=0;
for (i=1;i<=n; i++)
if ((i*i<=n)&&((i+1)*(i+1)>n)) m=i;
return m;
}
O(n)
Introduzione alla complessit `a, Paolo Bison, A.A. 2004-05, 2004-11-25 – p.10/20
Radice intera - II
metodo
static public int isqrtII(int n) {
int m;
m=1;
while ((m*m>n)||((m+1)*(m+1)<=n)) m = m+1;
return m;
}
O( √ n)
Radice intera - III
metodo
static public int isqrtIII(int n) {
int m,min,max;
min=1; max=n; m=(min+max)/2;
while (min!=max-1){
if (m*m>n) max=m;
else min=m;
m=(min+max)/2;
}
return m;
}
O (log n)
passo 1 2 . . . k . . . log 2 n
dim. n/2 n/4 . . . n/2 k . . . 1
radice intera - prestazioni
tempi di esecuzione in sec.
n √n I II III
500 22 5.44 0.38 0.16 5000 70 50.98 1.19 0.17 50000 223 547.77 3.79 0.21
programma III più efficiente, ma ...
I II III
√ 1000000 998215 1000 458753
Introduzione alla complessit `a, Paolo Bison, A.A. 2004-05, 2004-11-25 – p.13/20
Problemi P e NP
P problemi trattabili: soluzione data da un algoritmo di complessità al massimo polinomiale
NP una soluzione può essere verificata con un algoritmo a complessità polinomiale
NP-completi NP e nessun altro problema NP ha complessità maggiore a meno di una fattore polinomiale:
- soddisfacibilità di formule logiche - commesso viaggiatore
NP-hard intrinsecamente più difficili degli NP - ottimizzazione di problemi NP-completi:
- percorso minimo in un grafo
Introduzione alla complessit `a, Paolo Bison, A.A. 2004-05, 2004-11-25 – p.14/20
Soluzione di problemi NP
approccio esaustivo
generazione di tutte le possibili configurazioni di uscita
ricerca in questo spazio di una soluzione o di quella migliore
commesso viaggiatore
combinazione di tutti i percorsi possibili
ricerca della combinazione che soddisfa i vincoli
Generazione delle configurazioni - I
disposizione con ripetizione di N elementi for (i0=0;i0<N;i0++)
for (i1=0;i1<N;i1++) ....
for (iN_2=0;iN_2<N;iN_2++) for (iN_1=0;iN_1<N;iN_1++)
config(i0,i1,...,iN_2,iN_1)
O(N N )
numero dei for dipende dalla dimensione N
Generazione delle configurazioni - II
algoritmo ricorsivo
genera(int[] i, int liv, int N){
if (liv==N-1)
for(i[liv]=0;i[liv]<N;i[liv]++) config(i);
else for(i[liv]=0;i[liv]<N;i[liv]++) genera(i,liv+1,N);
}
attivazione
genera(i,0,N)
Introduzione alla complessit `a, Paolo Bison, A.A. 2004-05, 2004-11-25 – p.17/20
Generazione delle configurazioni - III
permutazioni semplici di N elementi
genera(int[] i, int[] ii, int liv){
int k,j,l;
if (ii.length==1){
i[liv]=ii[0];config(i); } else for(k=0;k<ii.length;k++){
i[liv]=ii[k];
int[] localii= new int[ii.length-1];
for (j = 0,l=0; j < ii.length; j++) if (j != k) localii[l++]=ii[j];
genera(i,localii,liv+1);
} } }
O(n!)
Introduzione alla complessit `a, Paolo Bison, A.A. 2004-05, 2004-11-25 – p.18/20
