Lezione del 7 marzo 2007 Complessità computazionale di un algoritmo Tornando alla nostra definizione di Time

Lezione del 7 marzo 2007

Complessità computazionale di un algoritmo

Tornando alla nostra definizione di TimeA(n), valore che indica il numero di operazioni elementari eseguite nel caso peggiore dall’algoritmo A su un input di dimensione n, possiamo considerare TimeA(n) come funzione della dimensione n e stimare la sua velocità di crescita trovando opportune funzioni g(n) tali che TimeA(n)=O(g(n)): diremo in tal caso che l’algoritmo A ha complessità computazionale O(g).

In particolare diremo che l’algoritmo A ha complessità computazionale polinomiale se la funzione TimeA(n) è di ordine polinomiale, e che l’algoritmo A ha complessità computazionale esponenziale se la funzione TimeA(n) è di ordine esponenziale: nel primo caso f=O(n^k) per un opportuno k intero 0, nel secondo f=O(aⁿ) per un’opportuna costante reale a>1.

Gli algoritmi di complessità polinomiale sono considerati più efficienti di quelli di complessità esponenziale, perché, al crescere della lunghezza n dell’input, il tempo di esecuzione nei primi cresce molto meno velocemente che nei secondi.

Tuttavia, per un fissato valore della lunghezza n dell’input, un algoritmo di complessità polinomiale può avere un tempo di esecuzione più alto di un algoritmo di complessità esponenziale.

Esempio: Siano dati l’algoritmo A con TimeA(n)=n⁷ di complessità polinomiale e l’algoritmo B con TimeA(n)=2ⁿ di complessità esponenziale. Per un input di lunghezza n=32 (quindi un input con 32 cifre binarie) l’algoritmo A esegue un massimo di 32⁷=2³⁵ operazioni, mentre l’algoritmo B esegue un massimo di 2³² (quindi un numero inferiore): se ogni operazione è eseguita in 1 milionesimo di secondo, l’algoritmo A impiega un massimo di circa 9 ore e mezza, l’algoritmo B un massimo di circa 1 ora e 12 minuti. Ma per un input di lunghezza doppia n=64 l’algoritmo A esegue un massimo di 64⁷ operazioni (circa 52 giorni), ma l’algoritmo B un massimo di 2⁶⁴ operazioni (circa 585.00 anni !!!).

E’ anche vero che un algoritmo di complessità polinomiale può essere egualmente “intrattabile”

perché ha tempi di esecuzione molto alti: se per esempio Time(n)=Cn^k allora Time(n)=O(n^k) ha complessità polinomiale, ma se la costante C è per esempio C=10¹⁰⁰⁰⁰ oppure l’esponente k è k=10000, il numero di operazioni elementari eseguite dall’algoritmo è “astronomico”.

Complessità di alcuni algoritmi aritmetici.

a) Costruiamo un algoritmo A=Somma(x,y) per calcolare la somma x+y di due numeri naturali x,y dati in input: supponiamo che, se n=L(x),m=L(y) sono le lunghezze binarie degli addendi, si abbia nm.

L’algoritmo di somma si può eseguire con gli stessi metodi che si usano per sommare numeri naturali rappresentati in base 10, utilizzando le operazioni elementari di somma sui singoli bits:

- si incolonna la rappresentazione binaria di y sotto quella di x, aggiungendo (se n>m) n-m bits=0 alla sinistra dei bits di y

- si inizializza il valore del riporto c=0

- procedendo da destra verso si sinistra si somma ogni bit di x con il bit dello stesso posto di y (con l’operazione elementare BitSum di somma di bits), ottenendo ad ogni passo una delle cifre binarie di x+y e un nuovo valore del riporto c

- se l’ultimo riporto è c=1 si aggiunge a sinistra un ulteriore bit=1 nel risultato x+y

- si esce con output x+y

Per esempio se x=(110011)2, y=(1101) allora:

110011+

001101 1000000

dunque il risultato della somma è x+y=(1000000)2. Schematizzando l’algoritmo:

1) input x=(an-1an-2…..a1a0)2 , y=(bm-1bm-2…..b1b0)2 con n=L(x) m=L(y) 2) se n>m si pone bm=bm+1=…=bn-1=0

3) c=0

4) per i=0,1…,n-1 si calcola BitSum(ai,bi,c)=(t,c1) e si pone zi=t, c=c1

5) se c=1 si pone zn=1

6) si esce con output x+y=(znzn-1…..z1z0)2

In tale algoritmo si eseguono n operazioni elementari, dunque TimeA(n)=O(n), e l’algoritmo ha complessità polinomiale (lineare).

b) Costruiamo un algoritmo A=Diff(x,y) per calcolare la differenza x-y di due numeri naturali x,y (con x>y) dati in input: se n=L(x),m=L(y) sono rispettivamente le lunghezze binarie, si avrà certamente nm.

Si può ricondurre il caso a quello dell’algoritmo Somma(x,y) con il seguente ragionamento:

consideriamo il numero binario y1 ottenuto da y sostituendo ogni bit 0 con 1 e viceversa e poi aggiungendo a sinistra (n-m) bits =1 (quindi y+y1 è un numero binario con n bits tutti=1 cioè y+y1=2ⁿ-1).

Si ha dunque y+(y1+1)=2ⁿ (y1+1 è il cosiddetto “complemento a 2 di y”) da cui x-y=x+(y1+1)-2ⁿ. Quindi per ottenere x-y basta sommare x con il complemento a 2 di y e poi sottrarre 2ⁿ al risultato (il che equivale ad elidere l’ultimo bit =1 a sinistra): poiché nel calcolo di x+(y1+1) (addendi lunghezza ≤n ) si esegue (vedere algoritmo Somma(x,y)) un numero n di operazioni elementari, si conclude che TimeA(n)=O(n), e anche questo algoritmo ha complessità polinomiale (lineare).

c) Costruiamo un algoritmo A=Prod(x,y) per calcolare il prodotto x+y di due numeri naturali x,y dati in input: supponiamo che, se n=L(x),m=L(y) sono le lunghezze binarie dei fattori, si abbia nm.

L’algoritmo di prodotto si può eseguire con gli stessi metodi che si usano per moltiplicare numeri naturali rappresentati in base 10, utilizzando le operazioni elementari di somma sui singoli bits.

Si costruiscono (al più) m righe (una riga in meno per ogni bit =0 in y) ognuna consistente nella copia del numero binario y shiftato opportunamente verso sinistra di un certo numero di posti (il che equivale ad aggiungere a destra dei bits =0) e si sommano tutte le righe (pensate come numeri binari): per contare il numero di operazioni elementari, supponiamo di sommare le righe 2 alla volta (la prima con la seconda, la terza con il risultato della somma della prima con la seconda etc.) eseguendo in totale un numero ≤m-1 di somme fra numeri di lunghezza ≤n+m, e poiché ognuna di tali somme corrisponde ad un numero ≤n+m di operazioni elementari di somma di bits, in totale il numero di operazioni elementari nell’algoritmo è ≤(n+m)(m-1)<n² ossia TimeA(n)=O(n²), e anche questo algoritmo ha complessità polinomiale (quadratica).

Per esempio se x=(11011)2, y=(1011) allora:

11011x 1011

11011 (si suppone di sommare la prima riga 11011 con la seconda 110110 e poi 110110 sommare il risultato con la terza riga 11011000)

11011000 100101001

dunque il risultato del prodotto è xy=(100101001)2.

Tale algoritmo di prodotto non è il più efficiente: esiste un algoritmo più sofisticato che ha complessità O(nlog(n)log(log(n))) “minore” di O(n²) (perché limnnlog(n)log(log(n))/n²=0).

Spesso, per i nostri scopi, ci limiteremo a costruire un algoritmo che risolva un problema senza indagare se sia il più efficiente in termini di complessità.

Aritmetica dei numeri naturali.

Nell’insieme N dei numeri naturali supporremo note le proprietà delle operazioni aritmetiche (somma, differenza, prodotto) e dell’ordinamento.

Ricordiamo fra le proprietà dell’insieme N dei numeri naturali il cosiddetto Assioma del buon ordinamento (o del minimo): in un qualunque sottoinsieme S non vuoto di N esiste sempre un minimo sS (tale che s≤x per ogni xS).

E’ ovvio che la stessa proprietà vale anche per ogni sottoinsieme non vuoto S di N{0}, in quanto se S contiene 0, allora 0 è il minimo in S.

Principio di induzione (I^a forma):

Sia P(n) una proprietà relativa ad un generico numero naturale n (si dice anche che P(n) è un predicato nella variabile n, con n che assume valori in N).

Se:

1) P(1) è vero

2) P(n) vero  P(n+1) vero allora P(n) è vero per ogni n in N.

Dimostrazione.

Per assurdo sia non vuoto l’insieme S di tutti i naturali n tali che P(n) è falso, e sia s il minimo in S.

Allora s>1, per l’ipotesi 1), dunque s-1N, e poiché s-1<s, si ha s-1S, dunque P(s-1) è vero, ossia P(s) è vero, per l’ipotesi 2), contraddizione.

Il numero 1 è detto anche base dell’induzione.

Esistono altre versioni dello stesso principio in cui la base dell’induzione può essere un fissato numero naturale n0: in tale caso l’ipotesi 1) diventa “P(n0) è vero”, l’ipotesi 2) diventa “P(n) vero  P(n+1) vero per ogni nn0”, la tesi diventa “P(n) è vero per ogni naturale nn0”.

Esiste anche una versione del principio di induzione riferita ad un predicato P(n) in cui la variabile n non assume tutti i valori naturali, ma solo i valori consecutivi da 1 a un naturale fissato n0, e in questo caso l’ipotesi 2) diventa “P(n) vero  P(n+1) vero per ogni n=1,….,n0-1”, e la tesi diventa

“P(n) è vero per ogni n=1,2,….,n0” . Principio di induzione (II^a forma):

Sia P(n) una proprietà relativa ad un generico numero naturale n.

1) P(1) è vero

2) P(k) vero per tutti i k=1,2,…,n-1  P(n) vero allora P(n) è vero per ogni n in N.

Dimostrazione.

Per assurdo sia non vuoto l’insieme S di tutti i naturali n tali che P(n) è falso, e sia s il minimo in S.

Allora s>1, per l’ipotesi 1), dunque 1,2,…s-1N, e poiché 1,2,…,s-1<s, si ha 1,2,…,s-1S. Dunque P(1), P(2), ……, P(s-1) sono veri, ossia P(s) è vero, per l’ipotesi 2), contraddizione.

Anche per questa forma del principio esistono altre versioni con base dell’induzione qualunque, o valide per un numero finito di valori di n.

Teorema dell’algoritmo della divisione per i numeri naturali.

Dati comunque i naturali a,b (a=dividendo, b=divisore), esistono e sono unici i numeri interi q,r0 (q=quoziente, r=resto) tali che a=bq+r, con r<b.

Dimostrazione.

Esistenza di q,r: Sia S={x0 / x=a-by, con y intero 0}. Poiché aS, tale S è sottoinsieme non vuoto di N{0}, e sia s il minimo in S. Si ha s0, s=a-by, con y intero 0, a=by+s. Se poniamo q=y, r=s, avremo la tesi se dimostreremo che s<b: se per assurdo fosse sb, si avrebbe s-b0, s-b=a- b(y+1)S, s-b<s, contraddizione.

Unicità di q,r: Dimostriamo prima l’unicità di r, supponendo per assurdo che sia a=bq+r=bq1+r1

con q,q1,r,r1 interi 0, r,r1<b, ed rr1 (per es. r>r1). Allora si avrebbe r-r1>0, r-r1r<b, r-r1=b(q1-q), quindi anche q1-q>0, cioè q1-q1, b(q1-q)b, contraddizione. Quindi è vero che r=r1. Da ciò si deduce anche 0=r-r1=b(q1-q), ossia q=q1 .

Dimostreremo ora che è possibile trovare quoziente e resto della divisione fra due numeri naturali, con un algoritmo di complessità polinomiale.

Se a=dividendo, b=divisore , possiamo assumere che sia ab (se a<b la divisione si effettua in modo banale con quoziente q=0, resto r=a).

Si ha allora certamente n=L(a)m=L(b).

La divisione di a per b si può effettuare con l’usuale algoritmo “scolastico”: il vantaggio di utilizzare cifre binarie 0,1 consiste nel fatto che la moltiplicazione di un numero per 1 dà come risultato il numero stesso, mentre per 0 dà come risultato 0.

Facciamo un esempio: siano a=(1101101)2, b=(101)2.

Prima “stacchiamo” (da sinistra) nel divisore a un “segmento” binario (di lunghezza minima) che non sia inferiore al divisore b (in questo caso è il segmento 110 di lunghezza 3) e sottraiamo da tale segmento il valore del divisore b, dando nello stesso tempo il valore 1 al primo bit del quoziente q:

1101101 101

101 1

1

In seguito “abbassiamo” il prossimo bit del dividendo, ma poiché otteniamo un numero 11 inferiore al divisore, diamo il valore 0 al secondo bit del quoziente q e “abbassiamo” un ulteriore bit ottenendo il numero 111 non inferiore al dividendo: diamo allora il valore 1 al terzo bit del quoziente e sottraiamo dal numero 111 così ottenuto il valore del divisore: 1101101 101

101 101

111

101

10

Di nuovo “abbassiamo” il prossimo bit del dividendo, ma poiché otteniamo un numero 100 inferiore al divisore, diamo il valore 0 al quarto bit del quoziente q e “abbassiamo” un ulteriore bit ottenendo il numero 1001 non inferiore al dividendo: diamo allora il valore 1 al quinto bit del quoziente e sottraiamo dal numero 1001 così ottenuto il valore del divisore:

1101101 101

101 10101

111

101

1001

101

100

Avendo ottenuto un valore 100 che è inferiore al divisore, l’algoritmo si ferma con output quoziente q=(10101)2 , e resto r=(100)2.

In generale se n=L(a)m=L(b), l’algoritmo esegue un numero di sottrazioni ≤n fra coppie di numeri di lunghezza ≤n , e poiché ognuna di tali sottrazioni ha (come visto nell’algoritmo Diff(x,y)) complessità lineare O(n), l’algoritmo della divisione ha complessità O(n²) quadratica, e dunque polinomiale.

L’algoritmo si può formalizzare nel modo seguente:

Sia n la dimensione di a, cioè il numero di cifre (binarie) di a:

a=an-12^n-1+an-22^n-2+…..+a12¹+a02⁰ dove ogni ai=0,1, an-1=1 .

In output avremo le cifre binarie del quoziente q= qn-12^n-1+qn-22^n-2+…..+q12¹+q02⁰ e il resto r<b (non è detto che il quoziente abbia esattamente dimensione n, perché alcune delle prime cifre qi

potranno essere =0).

L’algoritmo esegue i seguenti passi:

1) Si pone bn-1=1

2) Si esegue un ciclo di n-1 iterazioni, per i=1,….,n-1:

se bbn-i allora si pone qn-i=1, bn-i-1=2(bn-i-b)+an-i-1; in caso contrario si pone qn-i=0, bn-i-1=2bn-i+an-i-1

(tale ciclo definisce le cifre qn-1,….,q1, e costruisce i numeri bn-1,…,b0 ; notare che in ogni caso si ha bn-i-1=2(bn-i-bqn-i)+an-i-1 ad ogni iterazione)

3) Se bb0 allora si pone q0=1, r=bo-b; in caso contrario si pone q0=0, r=bo

(questo passo costruisce l’ultima cifra q0 del quoziente e il resto r; notare che in ogni caso si ha r=b0-bq0).

Posto q= qn-12^n-1+qn-22^n-2+…..+q12¹+q02⁰ , dobbiamo verificare che 0r<b, e che a=bq+r.

Si verifica per induzione che per ogni i>0 si ha:

bn-i=(an-12^i-1+an-22^i-2+…+an-i+12¹+an-i2⁰)-b(qn-12^i-1+qn-22^i-2+…+qn-i+12¹). (*) Infatti per i=1 si ha bn-1=1=an-1.

Supponendo vera la (*) per i, dimostriamola per i+1:

bn-(i+1)=bn-i-1=2(bn-i-bqn-i)+an-i-1=(an-12ⁱ+an-22^i-1+…+an-i2¹+an-i-12⁰)-b(qn-12ⁱ+qn-22^i-1+…+qn-i2¹) In particolare per i=n si ha:

b0=(an-12^n-1+an-22^n-2+…..+a12¹+a02⁰)-b(qn-12^n-1+qn-22^n-2+…+q12¹) da cui:

r=b0-bq0=(an-12^n-1+an-22^n-2+…..+a12¹+a02⁰)-b(qn-12^n-1+qn-22^n-2+…+q12¹+q02⁰)=a-bq . Inoltre si verifica per induzione che per ogni i>0 si ha:

0bn-i2b . (**)

Infatti per i=1 si ha 0bn-1=1<2b (perché b>0).

Supponendo vera la (**) per i, dimostriamola per i+1:

seguendo l’algoritmo, se bbn-i allora si ha bn-i-1=2(bn-i-b)+an-i-10 (essendo (bn-i-b),an-i-10), e inoltre bn-i-1=2(bn-i-b)+an-i-12(2b-1-b)+an-i-1=2b+(an-i-1-2)<2b (essendo an-i-1=0,1) ;

se invece b>bn-i allora si ha bn-i-1=2bn-i+an-i-10 (essendo bn-i,an-i-10) e inoltre bn-i-1=2bn-i+an-i-1

2(b-1)+ an-i-1=2b+(an-i-1-2)<2b (come sopra).