Tempo di calcolo e complessità asintotica PDF

Tempo di calcolo, complessità asintotica March 25, 2021 Obiettivi: introdurre le nozioni di tempo di calcolo e di confronto asintotico delle funzioni. Argomenti: caso peggiore, caso migliore e caso medio, notazione asintotica e le sue caratter...

Tempo di calcolo, complessità asintotica March 25, 2021 Obiettivi: introdurre le nozioni di tempo di calcolo e di confronto asintotico delle funzioni. Argomenti: caso peggiore, caso migliore e caso medio, notazione asintotica e le sue caratteristiche, comp- lessità di un problema. Ci interessa studiare gli algoritmi per capire quante risorse utilizzano. Risorse considerate: tempo, memoria, hardware (numero di processori). Si analizza il tempo di esecuzione per capire quanto tempo ci vuole per eseguire un algoritmo, caratterizzare la dimensione massima dell'ingresso di un'esecuzione ragionevole, scegliere fra i vari algoritmi che risolvono lo stesso problema, capire dove e come migliorare un certo algoritmo. Metodo di analisi: calcoliamo il numero di operazioni elementari eseguite. Sotto certe condizioni questa misura è proporzionale al tempo di esecuzione (ed è indipendente dal tipo di computer utilizzato e dal linguaggio di programmazione scelta per l'implementazione). Esempio visto durante lo studio degli algoritmi quadratici di ordinamento: la tabella riporta il numero di operazioni eseguite da Insertion-Sort e Selection-Sort nel caso migliore e peggiore (le costanti variano caso per caso). caso migliore caso peggiore Insertion-Sort an + b an2 + bn + c Selection-Sort an2 + bn + c an2 + bn + c (Con costanti a, b, c diversi caso per caso.) Fissata la dimensione del input, il numero di operazioni dipende (quasi sempre) dal input stesso! 0 Denotiamo con T (x) il numero di operazioni eseguite da un algoritmo con x in input. Numero di operazioni nel caso migliore con un input di dimensione n: Tcm (n) = min T 0 (x) ∀x:|x|=n cioè cerchiamo il minimo considerando tutti i possibili input di dimensione n. Numero di operazioni nel caso peggiore con un input di dimensione n: Tcp (n) = max T 0 (x) ∀x:|x|=n cioè cerchiamo il massimo considerando tutti i possibili input di dimensione n. Numero di operazioni nel caso medio con un input di dimensione n: X Tmedio (n) = p(x)T 0 (x) ∀x:|x|=n dove p(x) denota la probabilità che l'input è xe quindi si calcola la media del numero di operazioni con- siderando tutti i possibili input di dimensione n. 1 1 Confronto asintotico di funzioni e il suo utilizzo a caratterizzare la complessità di algoritmi Indichino T1 (n) e T2 (n) il numero di operazioni che due algoritmi devono eseguire per risolvere un certo problema nel caso di un input di dimensione n (caso migliore, caso peggiore o caso medio). Per confrontare algoritmi, dobbiamo confrontare tra loro funzioni. Esempio 1. Consideriamo n2 T1 (n) = , T2 (n) = 2n + 300 100 Quale algoritmo conviene utilizzare? Dipende da n: T1 (n) < T2 (n) se n < 300 e T1 (n) > T2 (n) se n > 300. Il primo algoritmo è conveniente in un numero nito di casi (n < 300). In un numero innito di casi conviene applicare il secondo algoritmo (n > 300). (Con n = 300 i due algoritmi equivalgono.) Esempio 2. Assumiamo di riuscire di dimezzare il numero di operazioni nel caso del primo algoritmo, cioè n2 T1 (n) = , T2 (n) = 2n + 300 200 Quale algoritmo conviene utilizzare? Dipende sempre da n: T1 (n) < T2 (n) se n < 517 e T1 (n) > T2 (n) altrimenti. Quindi anche se si migliora notevolmente il primo algoritmo, comunque esso è conveniente in un numero nito di casi (n < 517). In un numero innito di casi conviene applicare il secondo algoritmo (n ≥ 517). (Non esiste un numero intero n con il quale i due algoritmi equivalgono.) Esempio 3. Sia T (n) = 2n per un certo algoritmo e sia D la dimensione massima che si riesce a trattare con un certo computer dati i vincoli di tempo. Come cambia la dimensione massima trattabile se si usa un 0 computer 4 volte più veloce? Denotiamo con D la nuova dimensione massima. Abbiamo 0 2D = 2D 4 e quindi D0 = log2 4 + D = 2 + D Quindi anche usando un computer notevolmente più potente, la dimensione massima che si riesce a trattare si sposta di poco. In questo caso, moltiplicare la velocità per un costante conta poco. Conviene non considerare le costanti perché moltiplicando per una costante la dimensione massima di un problema trattabile cambia poco, il tipo di crescita di una funzione non dipende dalla scelta della costante, la stima esatta delle costanti è molto dicile in pratica. Lanotazione O (detto o grande) si utilizza per descrivere la crescita di una funzione trascurando costanti moltiplicative e un numero nito di valori. Denizione del O (limite superiore): f (n) ∈ O(g(n)) ⇐⇒ ∃c > 0, ∃n0 , ∀n > n0.f (n) ≤ cg(n) cioè f (n) è O di g(n) se e solo se esistono due costanti c > 0, n0 tali che per ogni n > n0 abbiamo f (n) ≤ cg(n). f (n) ∈ O(g(n)) signica che f (n) cresce, a parte un fattore costante (c) e trascurando un numero nito di valori (quelli ≤ n0 ), al massimo come la funzione g(n). 2 Esempio 4. Sia T (n) = an + b. Dimostriamo che con qualunque a > 0 e b si ha T (n) ∈ O(n). Applicando direttamente la denizione del O, dobbiamo trovare due costanti c > 0, n0 tali che ∀n > n0.an + b ≤ cn. Possiamo scegliere qualunque c > a e n0 = db/(c − a)e. Esempio 5. Sia T (n) = a2 n2 + a1 n + a0. a2 > 0, a1 , a0 si ha T (n) ∈ O(n2 ). Dimostriamo che con qualunque Applicando direttamente la denizione del O , dobbiamo trovare due costanti c > 0, n0 tali che ∀n > n0 2 2 abbiamo a2 n + a1 n + a0 ≤ cn. Possiamo scegliere qualunque c > a2 e n0 = dxe dove x è la soluzione 2 2 2 2 maggiore dell'equazione a2 x + a1 x + a0 = cx oppure n0 = 1 se l'equazione a2 x + a1 x + a0 = cx non ammette nessuna soluzione reale. Il seguente teorema è utile per dimostrare facilmente se una certa funzione f (n) sia O(g(n)) oppure no. Teorema: Se il limite f (n) a = lim n→∞ g(n) esiste allora 0 ≤ a < ∞ ⇐⇒ f (n) ∈ O(g(n)) Utilizzando il teorema precedente è facile dimostrare che ak nk + ak−1 nk−1 + · · · + a1 n + a0 ∈ O(nk ) e ak nk + ak−1 nk−1 + · · · + a1 n + a0 6∈ O(nk−1 ) se ak > 0 Per trovare la funzione più semplice g(n) tale che f (n) è O(g(n)) bisogna trovare il termine dominante di f (n) e trascurare i termini minori e le costanti moltiplicativi. Esempi: f (n) ∈ o 6∈ O(g(n)) k ∈ O(1) 85n + 123 ∈ O(n) 2n2 + n + 10 ∈ O(n2 ) Pk ai ni con ak > 0 ∈ O(nk ) Pi=0 k i h i=0 ai n con ak > 0 6 ∈ O(n ) se h < k 5n + log2 n + 5 ∈ O(n) n + 25 log2 n + 5 6 ∈ O(log2 n) Esempio 6. Base dei logaritmi. Cambiare la base dei logaritmi corrisponde a moltiplicare per una costante: 1 loga n = logb n logb a Di conseguenza si ha loga n ∈ O(logb n) ∀a > 1, ∀b > 1 Per questo motivo quando si usa la notazione O non si indica la base dei logaritmi, si scrive O(log n). La notazione O permette di confrontare le funzioni tra loro. La relazione. denita come f (n). g(n) ⇐⇒ f (n) ∈ O(g(n)) è un preordine basato sulla notazione O. Un preordine è una relazione riessiva, cioè f (n). f (n), ed è transitiva, cioè f (n). g(n) ∧ g(n). h(n) =⇒ f (n). h(n). Ma non permette di mettere in relazione 3 qualunque coppia di funzioni. Per esempio, con f (n) = sin(n) + 2, g(n) = cos(n) + 2 non si ha ne f (n). g(n) ne g(n). f (n). Si possono quindi ordinare le funzioni per velocità di crescita: 1e+006 1 log(n) 1/2 100000 n n n log(n) 10000 n23 nn 1000 2 100 10 1 2 4 6 8 10 12 14 16 18 20 n La notazione O è una notazione insiemistica. L'insieme O(g(n)) indica l'insieme di funzioni che sono O di g(n). Per esempio, l'insieme √ O(n) indica l'insieme di tutte le funzioni che crescono al massimo linearmente. Quindi le funzioni k, log2 n, n fanno parte dell'insieme O(n). In questa ottica insiemistica, il preordine stabilito dal O dà luogo ad una sequenza di inclusioni. Per esempio, O(1) ⊂ O(log n) ⊂ O(n1/2 ) ⊂ O(n) ⊂ O(n log n) ⊂ O(n2 ) ⊂ O(n2 log n) ⊂ O(n3 ) ⊂ O(2n ) Spesso la notazione O viene utilizzata in maniere informale: 2n2 + 6n = O(n2 ) 3n2 = O(n2 ) il che, presa alla lettera implicherebbe 2n2 + 6n = 3n2 che non è vero. f (n) = O(g(n)) si interpreta come un'equazione a senso unico, con cui rimpiazziamo una funzione con il suo ordine di grandezza. Per caratterizzare in senso O la complessità di algoritmi è conveniente utilizzare le seguenti regole: f (n) ∈ O(f (n)) cf (n) ∈ O(f (n)) c deve essere costante f (n) + f (n) ∈ O(f (n)) f (n) + g(n) ∈ O(f (n) + g(n)) f (n) ∈ O(g(n)) =⇒ ( f (n) + g(n) ∈ O(g(n)) ) f (n)g(n) ∈ O(f (n)g(n)) Con la notazione informale le regole diventano f (n) = O(f (n)) cf (n) = O(f (n)) c deve essere costante f (n) + O(f (n)) = O(f (n)) f (n) + O(g(n)) = O(f (n) + g(n)) f (n) = O(g(n)) =⇒ ( f (n) + O(g(n)) = O(g(n)) ) f (n)O(g(n)) = O(f (n)g(n)) Nota bene nf (n) 6∈ O(f (n)) perché n non è costante. 4 Esempio 7. Caratterizziamo in senso O la complessità del seguente algoritmo. 1: Alg(n) 2: s ← 0 3: for i ← 1 to 2n do 4: j←1 5: while j ≤ n do 6: j ←j+1 7: s←s+j 8: j←1 9: while j ≤ n do 10: j ← 2j 11: s ← s + ij 12: return s Contiamo il numero di operazioni T (n) considerando ogni riga come singola operazione.    T (n) 1 + n + 1 +n |{z} 1 + 2n + 1 +2n |{z} = |{z} 1 + |{z} 1  + |{z} 1 + | {z } | {z } r.2 r.3 r.4 r.5 r.6 r.7 r.8   blog nc + 2 +(blog2 nc + 1) |{z} 1  + |{z} 1 + |{z} 1 | 2{z } r.9 r.10 r.11 r.12 Applicando le regole si arriva a stabilire che T (n) ∈ O(n2 ). Con O si può dare un limite superiore per la velocità della crescita di una funzione. √ Questo limite non è necessariamente stretto: per esempio, n ∈ O(2n ). Per poter denire limiti stretti e limiti inferiori si introducono Θ (theta grande) e Ω (omega grande). Denizione del Θ (limiti stretti): f (n) ∈ Θ(g(n)) ⇐⇒ ∃c1 > 0, ∃c2 > 0, ∃n0 , ∀n > n0.c1 g(n) ≤ f (n) ≤ c2 g(n) cioè f (n) è Θ di g(n) se e solo se esistono tre costanti c1 > 0, c2 > 0, n0 tali che per ogni n > n0 abbiamo c1 g(n) ≤ f (n) ≤ c2 g(n). Denizione del Ω (limite inferiori): f (n) ∈ Ω(g(n)) ⇐⇒ ∃c > 0, ∃n0 , ∀n > n0.f (n) ≥ cg(n) cioè f (n) è Ω di g(n) se e solo se esistono due costanti c > 0, n0 tali che per ogni n > n0 abbiamo f (n) ≥ cg(n). Gracamente O, Ω e Θ: c2 g(n) cg(n) f (n) f (n) cg(n) f (n) c1 g(n) n0 n n0 n n0 n f (n) ∈ O(g(n)) f (n) ∈ Ω(g(n)) f (n) ∈ Θ(g(n)) 5 Segue direttamente dalle denizioni che f (n) ∈ Ω(g(n)) ∧ f (n) ∈ O(g(n)) ⇐⇒ f (n) ∈ Θ(g(n)) Come O, anche Ω denisce una relazione che è un preordine: f (n) & g(n) ⇐⇒ f (n) ∈ Ω(g(n)) La notazione Θ fornisce invece una relazione di equivalenza: f (n) ∼ g(n) ⇐⇒ f (n) ∈ Θ(g(n)) è riessiva, transitiva e anche simmetrica (f (n) ∈ Θ(g(n)) ⇐⇒ g(n) ∈ Θ(f (n))). Il teorema precedente esteso per Θ e Ω: Teorema: Se il limite f (n) a = lim n→∞ g(n) esiste allora 0≤a