Introduzione Introduzione Introduzione Algoritmi e strutture dati Obiettivo: stimare la complessità in tempo degli algoritmi Definizioni Modelli di calcolo Analisi di algoritmi Esempi di valutazioni Notazione Introduzione Perché? Alberto Montresor Per stimare il tempo impiegato per un dato input Per stimare il più grande input gestibile in tempi ragionevoli Università di Trento Per confrontare l’efficienza di algoritmi diversi 16 ottobre 2014 Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi Introduzione Per ottimizzare le parti più importanti 16 ottobre 2014 1 / 52 Alberto Montresor (UniTN) Definizioni Capitolo 2 - Analisi di algoritmi Introduzione Complessità Dimensione dell’input Definizione: Complessità: “Dimensione” → “Tempo” Criterio di costo logaritmico 16 ottobre 2014 2 / 52 Definizioni Come definire la dimensione del input? La taglia dell’input è il numero di bit necessari per rappresentarlo Come misurare il tempo? Esempio: moltiplicazione di numeri binari lunghi n bit Criterio di costo uniforme La taglia dell’input è il numero di elementi che lo costituiscono Esempio: ricerca minimo in un vettore di n elementi In molti casi... Possiamo assumere che gli “elementi” siano rappresentati da un numero costante di bit Le due misure coincidono a meno di una costante moltiplicativa Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 3 / 52 Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 4 / 52 Introduzione Definizioni Introduzione Definizioni Definizione di tempo Definizione di tempo Category:Models of computation Tempo ≡ wall-clock time Tempo n. operazioni elementari The category of≡ Computational Models lists abstract models for investigating computing machines. Standard computational models From Wikipedia, the free encyclopedia The main article for this category is Model of computation. assume discrete time paradigm. Il tempo effettivamente impiegato per eseguire un algoritmo Un’operazione si considera elementare se può essere eseguita in tempo Wikimedia Commons has media “costante” dal processore. related to Computational models. Dipende da troppi parametri: Subcategories Esempio (Operazioni elementari) bravura del programmatore This category has the following 14 subcategories, out of 14 total. linguaggio di programmazione utilizzato a *= 2 ? codice generato dal compilatore A processore, memoria (cache, primaria, secondaria) sistema operativo, processi attualmente in esecuzione Math.cos(d) ? D min(A, n) ? ▶► Denotational semantics (1 C, 7 ▶► Actor model (14 P) P) (5 P) E ▶► Automata (computation) (1 C, 1 Introduzione 5 / 52 Alberto Montresor (UniTN) S ▶► Lambda calculus (3 C, 46 P) T ▶► Stack machines (1 C, 8 P) Capitolo 2 - Analisi di algoritmi P Introduzione Modelli di calcolo – Definizione 16 ottobre 2014 ▶► Turing machine (26 P) 6 / 52 Modelli di calcolo – Definizione ▶► Persistence (2 C, 18 P) Modelli di calcolo Modelli di calcolo – Wikipedia ▶► Petri nets (15 P) Pages in category "Models of computation" Modello di calcolo The following 108 pages are in this category, out of 108 total. This list may not reflect recent changes (learn more). Rappresentazione astratta di un calcolatore Astrazione: deve permettere di nascondere i dettagli E cont. Realismo: deve riflettere la situazione reale Model of computation Potenza matematica: deve permettere di trarre conclusioni “formali” sul costo A Extended finite-state machine Abstract Job Object 7 / 52 Finite state transducer Algorithm characterizations Finite-state machine Alternating Turing machine FRACTRAN Alberto Montresor (UniTN) Pushdown automaton Quantum capacity Finite state machine with datapath Agent-based model Applicative computing systems 16 ottobre 2014 Probabilistic Turing machine Q F Abstract state machines B Capitolo 2 - Analisi di algoritmi P cont. Event-driven finite-state machine Evolution in Variable Environment Abstract machine Alberto Montresor (UniTN) (1 C, 12 P) L ▶► Combinatory logic (1 C, 8 P) 16 ottobre 2014 ▶► Register machines (1 C, 6 P) ▶► Educational abstract machines P) C Capitolo 2 - Analisi di algoritmi ▶► Process calculi (18 P) R ▶► Applicative computing systems Dobbiamo considerare una rappresentazione più astratta Alberto Montresor (UniTN) P cont. ▶► Abstract machines (1 P) Funnelsort H Capitolo 2 - Analisi di algoritmi Quantum circuit Quantum computer R Realization (systems) Register machine 16 ottobre 2014 8 / 52 Introduzione Modelli di calcolo – Definizione Introduzione Modelli di calcolo Modelli di calcolo Macchina di Turing Random Access Machine (RAM) Una macchina ideale che manipola i dati contenuti su un nastro di Macchina di Turingsecondo un insieme prefissato di regole. lunghezza infinita, Quantità infinita di celle di dimensione finita Accesso in tempo costante (indipendente dalla posizione) Processore (singolo) legge il simbolo sotto la testina Testina ⊥ Memoria: Ad ogni passo, la Macchina di Turing: Meccanismo di controllo Set di istruzioni elementari simile a quelli reali: Lamodifica macchina: il proprio stato interno ! legge il simbolo sotto la testina nuovo nella cella ! scrive modifica un il proprio statosimbolo (finito) interno ! scrive un nuovo simbolo nella cella muove la testina a destra o a sinistra ! muove la testina a destra o a sinistra a1 a2 a3 a4 Nastro Cella Marcatore della prima cella Modelli di calcolo – Definizione somme, addizioni, moltiplicazioni, operazioni logiche, etc. istruzioni di controllo (salti, salti condizionati) Costo delle istruzioni elementari Uniforme, ininfluente ai fini della valutazione (come vedremo) Fondamentale nello studio della calcolabilità Fondamentale nello studio della calcolabilità ✦ Non adatto per i nostri Livello troppo bassoscopi per i nostri scopi ✦ ✦ Livello troppo basso Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi ✦ Non sufficientemente realistico Introduzione 16 ottobre 2014 9 / 52 Alberto Montresor (UniTN) Esempi di analisi Capitolo 2 - Analisi di algoritmi Introduzione 16 ottobre 2014 10 / 52 Esempi di analisi 7 © Alberto Montresor Tempo di calcolo min() Tempo di calcolo binarySearch() Ogni istruzione richiede un tempo costante per essere eseguita Costante potenzialmente diversa da istruzione a istruzione Ogni istruzione viene eseguita un certo # di volte, dipendente da n Item min(Item[ ] A, integer n) Costo # Item min ← A[1] for integer i ← 2 to n do if A[i] < min then min ← A[i] c1 c2 c3 c4 1 n n−1 n−1 return min c5 1 T (n) = c1 + c2 n + c3 (n − 1) + c4 (n − 1) + c5 Il vettore viene suddiviso in due parti: Parte SX: b(n − 1)/2c Parte DX: bn/2c integer binarySearch(Item[ ] A, Item v, integer i, integer j) Costo # (i > j) # (i ≤ j) if i > j then c1 1 1 return 0 c2 1 0 else integer m ← b(i + j)/2c c3 0 1 if A[m] = v then c4 0 1 return m c5 0 0 else if A[m] < v then c6 0 1 return binarySearch(A, v, m + 1, j) c7 + T (bn/2c)c) 0 0/1 else return binarySearch(A, v, i, m − 1) c7 + T (b(n − 1)/2 0 1/0 = (c2 + c3 + c4 )n + (c1 + c5 − c3 − c4 ) = an + b Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 11 / 52 Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 12 / 52 Introduzione Esempi di analisi Introduzione Tempo di calcolo binarySearch() Soluzione della relazione di ricorrenza tramite sostituzione Assunzioni: Per semplicità, assumiamo n potenza di 2: n = 2k L’elemento cercato non è presente Ad ogni passo, scegliamo sempre la parte DX di dimensione n/2 T (n) = T (n/2) + d = T (n/4) + 2d = T (n/8) + 3d Due casi: i>j Esempi di analisi Tempo di calcolo binarySearch() (n = 0) ... T (n) = c1 + c2 = c n = 2k ⇒ k = log n = T (1) + kd i ≤ j (n > 0) T (n) = T (n/2) + c1 + c3 + c4 + c6 + c7 = T (n/2) + d Relazione di ricorrenza: ( c se n = 0 T (n) = T (n/2) + d se n ≥ 1 Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi Introduzione 16 ottobre 2014 13 / 52 = T (0) + (k + 1)d = kd + (c + d) = d log n + e. Alberto Montresor (UniTN) Notazione Capitolo 2 - Analisi di algoritmi Introduzione 16 ottobre 2014 Ordini di complessità Ordini di complessità Per ora, abbiamo analizzato precisamente due algoritmi e abbiamo ottenuto due funzioni di complessità: Per ora, abbiamo analizzato precisamente due algoritmi e abbiamo ottenuto due funzioni di complessità: Ricerca: T (n) = d log n + e Ricerca: T (n) = d log n + e logaritmica Minimo: T (n) = an + b Minimo: T (n) = an + b lineare Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 15 / 52 Alberto Montresor (UniTN) 14 / 52 Notazione Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 15 / 52 Introduzione Notazione Introduzione Notazione Ordini di complessità Ordini di complessità Per ora, abbiamo analizzato precisamente due algoritmi e abbiamo ottenuto due funzioni di complessità: Per ora, abbiamo analizzato precisamente due algoritmi e abbiamo ottenuto due funzioni di complessità: Ricerca: T (n) = d log n + e logaritmica Ricerca: T (n) = d log n + e logaritmica Minimo: T (n) = an + b lineare Minimo: T (n) = an + b lineare Una terza funzione deriva dall’algoritmo naïf per il minimo: Minimo: T (n) = f n2 + gn + h Una terza funzione deriva dall’algoritmo naïf per il minimo: Minimo: T (n) = f n2 + gn + h quadratica quadratica Notazione O(f (n)) – Limite superiore Un algoritmo ha complessità O(f (n)) se il suo tempo di esecuzione è limitato superiormente da una funzione di complessità f (n). Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi Introduzione 16 ottobre 2014 15 / 52 Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi Notazione Introduzione Ordini di complessità 15 / 52 Classi di complessità Per ora, abbiamo analizzato precisamente due algoritmi e abbiamo ottenuto due funzioni di complessità: Ricerca: T (n) = d log n + e logaritmica O(log n) Minimo: T (n) = an + b lineare O(n) f (n) log n √ n n n log n n2 n3 2n Una terza funzione deriva dall’algoritmo naïf per il minimo: Minimo: T (n) = f n2 + gn + h 16 ottobre 2014 Notazione quadratica O(n2 ) n = 101 3 3 10 30 102 103 1024 n = 102 6 10 100 664 104 106 1030 n = 103 9 31 1000 9965 106 109 10300 n = 104 13 100 10000 132877 108 1012 103000 Tipo logaritmico sublineare lineare loglineare quadratico cubico esponenziale Notazione O(f (n)) – Limite superiore Un algoritmo ha complessità O(f (n)) se il suo tempo di esecuzione è limitato superiormente da una funzione di complessità f (n). Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 15 / 52 Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 16 / 52 Complessità problemi vs algoritmi Complessità problemi vs algoritmi Introduzione Algoritmi e strutture dati Obiettivo: riflettere sulla complessità dei problemi e degli algoritmi In alcuni casi, si può migliorare quanto si ritiene “normale” In altri casi, è impossibile fare di meglio Analisi di algoritmi Complessità algoritmi vs Complessità problemi Qual è il rapporto fra un problema computazionale e l’algoritmo? Back to basics! Alberto Montresor Somme Moltiplicazioni Università di Trento 16 ottobre 2014 Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 17 / 52 Complessità problemi vs algoritmi Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 18 / 52 Complessità problemi vs algoritmi Moltiplicare numeri complessi Moltiplicare numeri complessi Questioni aperte... Moltiplicazione numeri complessi Si può fare di meglio? Oppure, è possibile dimostrare che non si può fare di meglio? (a + bi)(c + di) = [ac − bd] + [ad + bc]i Input: a, b, c, d Alcune riflessioni Output: ac − bd, ad + bc Domande Considerate un modello di calcolo dove la moltiplicazione costa 1, le addizioni/sottrazioni costano 0.01. In questo modello, effettuare 3 moltiplicazioni invece di 4 risparmia il 25% del costo Esistono contesti in cui effettuare 3 moltiplicazioni invece di 4 può produrre un risparmio maggiore Quanto costa l’algoritmo dettato dalla definizione? Potete fare di meglio? Qual è il ruolo del modello di calcolo? Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 19 / 52 Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 20 / 52 Complessità problemi vs algoritmi Complessità problemi vs algoritmi Sommare numeri binari Limite inferiore alla complessità di un problema Algoritmo elementare della somma – sum() Sommare numeri binari Notazione Ω(f (n)) – Limite inferiore richiede di esaminare tutti gli n bit Algoritmo elementare della somma - sum() tre bit e generare riporto) costo totale cn (c ≡ costo per sommare ✦ ✦ Domanda ✦ costo totale cn (c ≡ costo per sommare tre bit e generare riporto) Limite inferiore della somma di numeri binari Esiste ✦unDomanda metodo più efficiente? ✦ Un problema ha complessità Ω(f (n)) se tutti i possibili algoritmi che lo risolvono hanno complessità f (n) o superiore. richiede di esaminare tutti gli n bit Il problema della somma di numeri binari ha complessità Ω(n). Esiste un metodo più efficiente? 11101111111111 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1+ 111101101101011 1101010100100010 Alberto Montresor (UniTN) © Alberto Montresor Complessità Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 21 / 52 18 problemi vs algoritmi Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi Moltiplicare numeri binari Algoritmi aritmetici Algoritmo elementare della somma – prod() Confronto della complessità computazionale moltiplicazione di ogni bit con ogni altro bit Somma : Tsum (n) = O(n) costo totale cn Prodotto : Tprod (n) = O(n2 ) Moltiplicare numeri binari 2 ✦ 16 ottobre 2014 22 / 52 Complessità problemi vs algoritmi Algoritmo “elementare” del prodotto - prod() n2 Alberto Montresor (UniTN) ******* ******* ******* ******* ******* ******* ******* ******* ******* Capitolo 2 - Analisi di algoritmi Si potrebbe erroneamente concludere che... x 16 ottobre 2014 Il problema della moltiplicazione è inerentemente più costoso del problema dell’addizione “Conferma” la nostra esperienza 23 / 52 Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 24 / 52 Complessità problemi vs algoritmi Complessità problemi vs algoritmi Algoritmi aritmetici Moltiplicare numeribinari binari Moltiplicare numeri Confronto fra problemi Per provare che il problema del prodotto è più costoso del problema della somma, dobbiamo provare che non esiste una soluzione in tempo lineare per il prodotto ✦ Un metodo algoritmico: divide-et-impera Divide-et-impera ✦ Divide: dividi il problema in in sottoproblemi di di dimensioni inferiori Divide: dividi il problema sottoproblemi dimensioni inferiori Impera: risolvi i sottoproblemi in maniera ricorsiva ✦ Impera: risolvi i sottoproblemi in maniera ricorsiva Combina: unisci le soluzioni dei sottoproblemi in modo da ottenere unisci le soluzioni dei sottoproblemi in modo da ottenere la Combina: risposta del problema principale ✦ Abbiamo confrontato gli algoritmi, non i problemi! Sappiamo solo che l’algoritmo di somma studiato alle elementari è più efficiente dell’algoritmo del prodotto studiato alle elementari risposta del problema principale Moltiplicazione divide-et-impera ✦ Moltiplicazione ricorsiva n/2 + XX==aa· 2n/2 +bb ✦ Nel 1960, Kolmogorov enunciò in una conferenza che la moltiplicazione ha limite inferiore Ω(n2 ) ✦ XY = ac 2 + (ad+bc) 2 ✦ Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi Y Y==cc· 2 2n/2 +dd n/2 + n/2 XY = ac · 2n n+ (ad + bc) · 2n/2 + bd ✦ Una settimana dopo, fu provato il contrario! 16 ottobre 2014 25 / 52 Complessità problemi vs algoritmi + bd X a b Y c d Nota: ✦ Moltiplicare per 2t ≡ shift di t posizioni, in tempo lineare 16 ottobre 2014 26 / 52 Sommare due vettori di bit anch’esso in tempo lineare Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi ✦ Complessità problemi vs algoritmi Svolgere la ricorsione Analisi della ricorsione Moltiplicare numeri binari tramite Divide-et-impera © Alberto Montresor 0 if n = 1 then return X[1] · Y [1] else spezza X in a; b e Y in c; d return pdi(a, c, n/2) · 2n + (pdi(a, d, n/2) + pdi(b, c, n/2)) · 2n/2 + pdi(b, d, n/2) T (n) = Nota: Moltiplicare per n/2 n/2 n/4 n/4 i log2 n n/4 n/4 n/4 n/4 n/2 n/4 n/4 + n/2 n/4 n/2 n/4 n/4 c2 · 4 · n/2 n/2 n/4 n/4 n/4 n/4 c2 · 42 · n/22 c2 · 4i · n/2i ............................................................................ 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1 16 ottobre 2014 T (1) · 4log n = c1 · nlog 4 ≡ shift di t posizioni, in tempo lineare Capitolo 2 - Analisi di algoritmi n/4 n/2 n/2 + Livello i: 4i istanze n/24ii copies of n/2i Leveldii dimensione is the sum of T (n) = Alberto Montresor (UniTN) + .......................... c1 n=1 4T (n/2) + c2 · n n > 1 2t 1 2 c2 · 1 · n nn boolean [ ] pdi(boolean[ ] X, boolean[ ] Y , integer n) 27 / 52 ⇢ c1 4T (n/2) + c2 · n Alberto Montresor (UniTN) n=1 n>1 Capitolo 2 - Analisi di algoritmi = c1 · n2 16 ottobre 2014 28 / 52 Complessità problemi vs algoritmi Complessità problemi vs algoritmi Moltiplicare numeri binari Moltiplicazione di Karatsuba (1962) A1 = ac Confronto della complessità computazionale A3 = bd Prodotto : Tprod (n) = O(n2 ) m = (a + b)(c + d) = ac + ad + bc + bd Prodotto : Tpdi (n) = O(n2 ) A2 = m − A1 − A3 = ad + bc Tutto questo lavoro per nulla? boolean [ ] karatsuba(boolean[ ] X, boolean[ ] Y , integer n) if n = 1 then return X[1] · Y [1] else spezza X in a; b e Y in c; d boolean[ ] A1 ← karatsuba(a, c, n/2) boolean[ ] A3 ← karatsuba(b, d, n/2) boolean[ ] m ← karatsuba(a + b, c + d, n/2) boolean[ ] A2 ← m − A1 − A3 return A1 · 2n + A2 · 2n/2 + A3 Domanda: E’ possibile fare meglio diecosì? Algoritmi Strutture di Dati Notate che la versione ricorsiva chiama se stessa 4 volte. n)) , 9c > 0, m > 0 : g(n) cf (n), 8n m n)) , 9c > 0, m > 0 : cf (n) g(n), 8n m n)) , 9c > 0, d > 0, m > 0 : cf (n) g(n) df (n), 8n m boolean[ ] X, boolean[ ] Y , integer n) Alberto Montresor (UniTN) [1] · Y [1] Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 29 / 52 Complessità problemi vs algoritmi Analisi della ricorsione 0 1 [1] · Y [1] 2 n/4 c2 · 1 · n nn n/4 + n/2 + n/2 n/2 n/4 n/4 n/4 + n/2 n/4 n/4 n/4 c2 · 32 · n/22 n/4 T (n) = n=1 n>1 c1 3T (n/2) + c2 · n n=1 n>1 Alberto Montresor ⇢ (UniTN) Capitolo 2 - Analisi di algoritmi Es. Tkara (106 ) = 3 · 109 L’algoritmo “naif” non è sempre il migliore ... ... a meno che non sia possibile dimostrare il contrario! ............................................................................ ⇢ c1 4T (n/2) + c2 · n Es. Tprod (106 ) = 1012 Prodotto : Tkara (n) = O(n1.58... ) ... può esistere spazio di miglioramento ... 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1 ⇢ Prodotto : Tprod (n) = O(n2 ) Conclusioni c2 · 3i · n/2i .......................... T (n) = 30 / 52 Confronto della complessità computazionale c2 · 3 · n/2 n/2 in a; b e Y in c; d A1 KARATSUBA (a, c, n/2) A3 i KARATSUBA(b, d, n/2) Livello i: 3i istanze n/24ii copies of n/2i Leveldii dimensione is the sum of m KARATSUBA (a + b, c + d, n/2) A2 m A1 A3 1 · 2n + A2 · 2n/2 + A3 log2 n 16 ottobre 2014 Moltiplicare numeri binari X, boolean[ ] Y , integer n) n/2n/2 Capitolo 2 - Analisi di algoritmi Complessità problemi vs algoritmi in a; b e Y in c; d Svolgere la ricorsione I (a, c, n/2) · 2n + ( PDI (a, d, n/2) + PDI (b, c, n/2)) · 2n/2 + PDI (b, d, n/2) RATSUBA (boolean[ ] Alberto Montresor (UniTN) log n T (1) · 3 = c1 · nlog 3 = n1.58... 16 ottobre 2014 31 / 52 Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 32 / 52 Complessità problemi vs algoritmi Complessità problemi vs algoritmi Non finisce qui . . . GNU Multiple Precision Arithmetic Library GMP Utilizzata da Mathematica, Maple, etc. MUL_FFT_THRESHOLD «Arithmetic without limitations» Toom-Cook (1963) Utilizza Schönhage–Strassen quando l’input è più lungo di k parole di 64 bit, con k dipendente dall’architettura Noto come algoritmo Toom3, ha complessità O(nlog 5/ log 3 ) ≈ O(n1.465 ) Karatsuba = Toom2 Moltiplicazione normale = Toom1 Schönhage–Strassen (1971) Complessità O(n · log n · log log n) Basato su Fast Fourier Transforms Martin Fürer (2007) Complessità O(n · log n · 2O(log ∗ n) ) Limite inferiore: Ω(n log n) (congettura) Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 33 / 52 Algoritmi di ordinamento meas conf host type abi host name thres thres z10-ibm-linux-gnu 64 lgentoo4.s390.gentoo.wh0rd.org-stat 1728 1728 atom-unknown-linux-gnu 64 gege.gmplib.org-stat 2240 2240 z10esa-ibm-linux-gnu 32 lgentoo3.s390.gentoo.wh0rd.org-stat 2240 2240 power7-unknown-linux-gnu mode32 gcc1-power7.osuosl.org-stat 2688 2688 bulldozer-unknown-freebsd8.3 64 oshell.gmplib.org-stat 3520 3712 piledriver-unknown-netbsd6.1.3 64 pilenbsd64v61.gmplib.org-stat 3712 3712 powerpc7447-unknown-linux-gnu 32 spigg.gmplib.org-stat 3712 3712 coreihwl-unknown-netbsd6.1.2 64 hannahnbsd64v61.gmplib.org-stat 4224 4224 coreinhm-unknown-netbsd6.1.3 64 bikonbsd64v61.gmplib.org-stat 4224 4032 power7-ibm-aix7.1.0.0 mode64 power-aix.fsffrance.org-stat 4288 4288 atom-unknown-linux-gnu 32 gege.gmplib.org-stat 4544 4544 core2-unknown-netbsd6.1.4 64 repentiumnbsd64v61.gmplib.org-stat 4736 4736 coreisbr-apple-darwin12.5.0 64 poire.loria.fr-stat 4736 4736 coreiwsm-unknown-linux-gnu 64 gcc20.fsffrance.org-stat 4736 4032 power7-unknown-linux-gnu mode64 gcc1-power7.osuosl.org-stat 4736 4288 powerpc970-apple-darwin8.11.0 mode32 g5.gmplib.org-stat 4736 2688 power7-ibm-aix7.1.0.0 32 power-aix.fsffrance.org-stat 5312 5312 bobcat-unknown-netbsd6.1.3 64 bobcat.gmplib.org-stat 5504 5504 alphaev6-unknown-linux-gnu standard agnesi.math.su.se-stat 5760 5760 armcortexa15neon-unknown-linux- standard parma.gmplib.org-stat 5760 5760 power7-unknown-linux-gnu 32 gcc1-power7.osuosl.org-stat 5760 5312 Alberto Montresor (UniTN)32 Capitolo 2 - Analisi di algoritmi core2-unknown-netbsdelf6.1.4 repentiumnbsd32v61.gmplib.org-stat 6784 6784 coreinhm-unknown-netbsdelf6.1.3 Algoritmi 32 6784 6784 dibikonbsd32v61.gmplib.org-stat ordinamento coreiwsm-unknown-linux-gnu 32 gcc20.fsffrance.org-stat 6784 6784 k10-unknown-netbsdelf6.1.2 32 tigernbsd32v61.gmplib.org-stat 6784 6784 powerpc970-apple-darwin8.11.0 32 g5.gmplib.org-stat 6784 6784 coreihwl-unknown-netbsdelf6.1.2 32 hannahnbsd32v61.gmplib.org-stat 7424 7424 athlon-unknown-netbsdelf6.1.4 32 tambo.gmplib.org-stat 7552 7808 bobcat-unknown-netbsd6.1.3 32 bobcat.gmplib.org-stat 7552 7552 k10-unknown-netbsd6.1.2 64 tigernbsd64v61.gmplib.org-stat 7552 7808 pentium4-unknown-netbsdelf6.1.4 32 parks.gmplib.org-stat 7552 7808 piledriver-unknown-netbsdelf6.1 32 pilenbsd32v61.gmplib.org-stat 7552 6784 athlon-pc-linux-gnu 32 shell.math.su.se 7808 7808 k8-unknown-linux-gnu 64 gcc12.fsffrance.org-stat 7808 11520 powerpc970-apple-darwin8.11.0 mode64 g5.gmplib.org-stat 9088 9088 k10-unknown-freebsd9.2 64 shell.gmplib.org-stat 9344 7808 number of hosts: 36 med: 5504 med: 5312 cfg/meas avg: 0.98797 Introduzione Algoritmi e strutture dati Obiettivo: valutare gli algoritmi in base alla tipologia dell’input In alcuni casi, gli algoritmi si comportano diversamente a seconda delle caratteristiche dell’input Conoscere in anticipo tali caratteristiche permette di scegliere il miglior algoritmo in quella situazione Il problema dell’ordinamento è una buona palestra dove mostrare configured thresholds are up in the sky configured thresholds get a green light questi concetti Analisi di algoritmi Algoritmi di ordinamento Please send comments about this page to gmp-discuss at gmplib.org Copyright 2000-2014 Free Software Foundation Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved. Algoritmi d’ordinamento Università di Trento Selection Sort Insertion Sort Merge Sort Counting Sort 16 ottobre 2014 Capitolo 2 - Analisi di algoritmi Table generated: 2014-08-25 08:57:15 (UTC) configured thresholds are down in the mud Alberto Montresor Alberto Montresor (UniTN) cfg file s390_64/z10/gmp-mparam.h x86_64/atom/gmp-mparam.h s390_32/esame/gmp-mparam.h powerpc64/mode32/p4/gmp-mparam.h x86_64/bd1/gmp-mparam.h x86_64/bd2/gmp-mparam.h powerpc32/gmp-mparam.h x86_64/coreihwl/gmp-mparam.h x86_64/coreinhm/gmp-mparam.h powerpc64/mode64/p7/gmp-mparam.h x86/atom/gmp-mparam.h x86_64/core2/gmp-mparam.h x86_64/coreisbr/gmp-mparam.h x86_64/coreinhm/gmp-mparam.h powerpc64/mode64/p7/gmp-mparam.h powerpc64/mode32/p4/gmp-mparam.h powerpc32/p7/gmp-mparam.h x86_64/bobcat/gmp-mparam.h alpha/ev6/gmp-mparam.h arm/v7a/cora15/gmp-mparam.h powerpc32/p7/gmp-mparam.h 16 ottobre 2014 34 / 52 x86/core2/gmp-mparam.h x86/coreinhm/gmp-mparam.h x86/coreinhm/gmp-mparam.h x86/k10/gmp-mparam.h powerpc32/p4/gmp-mparam.h x86/coreisbr/gmp-mparam.h x86/k7/gmp-mparam.h x86/bobcat/gmp-mparam.h x86_64/k10/gmp-mparam.h x86/pentium4/sse2/gmp-mparam.h x86/bd2/gmp-mparam.h x86/k7/gmp-mparam.h x86_64/k8/gmp-mparam.h powerpc64/mode64/p4/gmp-mparam.h x86_64/k10/gmp-mparam.h 16 ottobre 2014 35 / 52 Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 36 / 52 Algoritmi di ordinamento Algoritmi di ordinamento Tipologia di analisi Ordinamento Analisi del caso pessimo Problema dell’ordinamento La più importante Il tempo di esecuzione nel caso peggiore è un limite superiore al tempo di esecuzione per qualsiasi input Per alcuni algoritmi, il caso peggiore si verifica molto spesso Es.: ricerca di dati non presenti in un database Problema Input: Una sequenza A = a1 , a2 , . . . , an di n numeri Output: Una sequenza B = b1 , b2 , . . . , bn che sia una permutazione di A e tale per cui b1 ≤ b2 ≤ . . . ≤ bn Approccio “demente”: Genero tutte le possibili permutazioni fino a quando non ne trovo una già ordinata Analisi del caso medio Difficile in alcuni casi: cosa si intende per “medio”? Distribuzione uniforme Analisi del caso ottimo Può avere senso se si conoscono informazioni particolari sull’input Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi Algoritmi di ordinamento 16 ottobre 2014 37 / 52 Alberto Montresor (UniTN) Problema Capitolo 2 - Analisi di algoritmi Algoritmi di ordinamento Ordinamento Selection Sort Problema dell’ordinamento selectionSort(Item[ ] A, integer n) Input: Una sequenza A = a1 , a2 , . . . , an di n numeri 16 ottobre 2014 38 / 52 Selection Sort for i ← 1 to n − 1 do integer min ← min(A, i, n) A[i] ↔ A[min] Output: Una sequenza B = b1 , b2 , . . . , bn che sia una permutazione di A e tale per cui b1 ≤ b2 ≤ . . . ≤ bn Approccio “demente”: Genero tutte le possibili permutazioni fino a quando non ne trovo una già ordinata Approccio “naif”: integer min(Item[ ] A, integer i, integer n) integer min ← i % Posizione del minimo parziale for j ← i + 1 to n do if A[j] < A[min] then min ← j % Nuovo minimo parziale return min Complessità nel caso medio, pessimo, ottimo? Cerco il minimo e lo metto in posizione corretta, riducendo il problema agli n − 1 restanti valori. Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 38 / 52 Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 39 / 52 Algoritmi di ordinamento Selection Sort Algoritmi di ordinamento Selection Sort 001_207_13_DEAGO_Algoritmi_OK Insertion Sort Algoritmo efficiente per ordinare piccoli insiemi di elementi Si basa sul principio di ordinamento di una “mano“ di carte da gioco (e.g. scala quaranta) selectionSort(Item[ ] A, integer n) for i ← 1 to n − 1 do integer min ← min(A, i, n) A[i] ↔ A[min] for i ← 2 to n do Item temp ← A[i] integer j ← i while j > 1 and A[j − 1] > temp do A[j] ← A[j − 1] j ←j−1 A[j] ← temp Complessità nel caso medio, pessimo, ottimo? i=1 (n − i) = i X = i=1 Alberto Montresor (UniTN) n(n − 1) = n2 − n/2 = O(n2 ) 2 Capitolo 2 - Analisi di algoritmi Algoritmi di ordinamento Ana 1 2 3 4 5 6 7 insertionSort(Item[ ] A, integer n) integer min(Item[ ] A, integer i, integer n) integer min ← i % Posizione del minimo parziale for j ← i + 1 to n do if A[j] < A[min] then min ← j % Nuovo minimo parziale return min n−1 X Insertion Sort 28/01/14 12:25 Pagina 29 7 4 2 1 8 3 5 4 7 2 1 8 3 5 2 4 7 1 8 3 5 1 2 4 7 8 3 5 1 2 4 7 8 3 5 1 2 3 4 7 8 5 1 2 3 4 5 7 8 16 ottobre 2014 39 / 52 Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 Fig. 2.2 Esecuzione della procedura insertionSort(). Insertion Sort Algoritmi di ordinamento 2.6 Complessità Merge Sort In questo algoritmo Divide et impera 40 / 52 Merge Sort ESEMPIO – [Insertion sort] La Fig. 2.2 mostra l’ordinamento della sequenza di elementi 7 dura insertionSort(). La complessità della procedura dipende dalla disposizione ini Merge Sort è basato sulla tecnica divide-et-impera in precedenza so peggiore si ha quando il vettore Avista è ordinato alla rovescia; Divide: Spezza virtualmente il vettore di deve n elementi in due trasferito in zione del for, l’elemento temp essere sempre sottovettori di n/2 elementi richiederà i spostamenti e la complessità della procedura è O( nate, però, la procedura insertionSortsui () èdue H(n), poiché la cond Combina: Chiama Merge Sort ricorsivamente sottovettori sempre falsa. Impera: Unisci (merge) le due sequenze ordinate Il costo di esecuzione non dipende solo dalla dimensione... ma anche dalla distribuzione dei dati in ingresso Domande Qual è il costo nel caso il vettore sia già ordinato? Qual è il costo nel caso il vettore sia ordinato in ordine inverso? Possiamo fare di meglio, diminuendo la complessità in tutti i ca mo? La risposta è positiva. L’algoritmo Merge Sort è basato su Bisogna sfruttare 2.4): il fatto che i due sottovettori sono già ordinati Cosa succede “in media”? (informalmente) Idea Dividi il vettore in due sequenze di n/2 elementi ciascuno, ord poi “fondi” le due metà ordinate in un’unica sequenza ordina Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 41 / 52 Capitolo 2 - AnalisiMergeSort di algoritmi (), da chiamare 16 ottobre 2014 42 / 52 La procedura ricorsiva con l’istruzio Alberto Montresor (UniTN) Algoritmi di ordinamento Merge Sort Algoritmi di ordinamento Merge Sort Funzionamento Merge() Merge Merge Sort primo 1 mezzo ultimo n i j k B 1 3 7 8 2 4 6 9 i j k A B 1 3 7 8 2 4 6 9 j i k A B 1 2 3 7 8 4 6 9 i j k A B 1 2 3 7 8 4 6 9 i j k A B 1 2 3 4 7 8 6 9 j i k A B 1 2 3 4 6 7 8 9 Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 Merge Sort j k i Algoritmi di ordinamento A B 1 2 3 4 6 7 8 9 Merge() i j k A B 1 2 3 4 6 7 8 9integer ultimo, Merge (Item A[ ], integer primo, integer mezzo) 37 k integer i, j, k, h iA ← primo; j ← mezzo + 1; k ← primo B 1 2 3 4 6 7 8 1 2 3 4 6 7 8 9 while i ≤ mezzo and j ≤ ultimo do A Merge(integer[ ] Input: Merge A, integer primo, integer ultimo, integer mezzo) Sort A è un vettore di n interi i k ≤ mezzo < ultimo ≤ n primo, ultimo, jmezzo sono tali che 1 ≤ primo +1 . . . ultimo ] sono A I 1sottovettori B 3 7 8 A[primo 2 4 6 . .9. mezzo ] e A[mezzo già ordinati i j 3 7 8 2 4 6 9 Output: A A k B 1 I due sottovettori sono fusi in un unico sottovettore ordinato i . . . ultimoj ] tramite un vettore di appoggio k B A[primo B 1 3 7 8 4 6 9 Capitolo 2 - Analisi di algoritmi i j Algoritmi di ordinamento Merge Sort A B 1 7 8 4 6 9 Funzionamento Merge() i j A B 1 7 8 6 9 j i tresor A B 1 7 8 9 j i A B 1 8 9 i j A B 1 9 2 k Alberto Montresor (UniTN) A 1 2 3 4 6 7 8 9 B 16 ottobre 2014 43 / 52 2 3 k 2 3 4 k 2 3 4 6 k if A[i] ≤ A[j] then B[k] ← A[i] 2 3 4 6 7 k 2 3 4 6 7 8 k 1 2 3 4 6 7 8 © Alberto Montresor i←i+1 else B[k] ← A[j] j ←j+1 k ←k+1 j ← ultimo for h ← mezzo downto i do A[j] ← A[h] 37 j ←j−1 for j ← primo to k − 1 do A[j] ← B[j] © Alberto Montresor Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 44 / 52 45 / 52 Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 46 / 52 Algoritmi di ordinamento Merge Sort Algoritmi di ordinamento Merge Sort Costo computazionale Costo computazionale Domanda Domanda Qual è il costo computazionale di Merge()? Qual è il costo computazionale di Merge()? ⇒ O(n) Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi Algoritmi di ordinamento 16 ottobre 2014 47 / 52 Alberto Montresor (UniTN) Merge Sort Capitolo 2 - Analisi di algoritmi Algoritmi di ordinamento 16 ottobre 2014 47 / 52 Merge Sort Merge(): Partizionamento Merge Sort Programma completo: 33, 21, 7, 48, 28, 13, 65, 17 Chiama ricorsivamente se stesso e usa Merge() per unire i risultati Caso base: sequenze di lunghezza ≤ 1 sono già ordinate 33, 21, 7, 48 28, 13, 65, 17 MergeSort(Item A[ ], integer primo, integer ultimo) 33, 21 if primo < ultimo then integer mezzo ← b(primo + ultimo)/2c MergeSort(A, primo, mezzo) MergeSort(A, mezzo + 1, ultimo) Merge(A, primo, ultimo, mezzo) Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 33 16 ottobre 2014 48 / 52 7, 48 21 Alberto Montresor (UniTN) 7 28, 13 48 28 Capitolo 2 - Analisi di algoritmi 65, 17 13 65 16 ottobre 2014 17 49 / 52 Algoritmi di ordinamento Merge Sort Algoritmi di ordinamento Merge(): ricorsione Merge Sort Analisi di MergeSort() 7, 13, 17, 21, 28, 33, 48, 65 Un’assunzione semplificativa: n = 2k , ovvero l’altezza dell’albero di suddivisioni è esattamente k = log n; 7, 21, 33, 48 21, 33 13, 17, 28, 65 7, 48 13, 28 Tutti i sottovettori hanno dimensioni che sono potenze esatte di 2 Costo computazionale: O(n log n) 17, 65 T (n) = 33 21 7 Alberto Montresor (UniTN) 48 28 Capitolo 2 - Analisi di algoritmi Algoritmi di ordinamento 13 65 16 ottobre 2014 17 50 / 52 ( c n=1 2T (n/2) + dn n > 1 Alberto Montresor (UniTN) Merge Sort Capitolo 2 - Analisi di algoritmi Algoritmi di ordinamento 16 ottobre 2014 Costo computazionale di Merge Sort Costo computazionale di Merge Sort Domanda Domanda Qual è il costo computazionale di MergeSort()? Qual è il costo computazionale di MergeSort()? ⇒ O(n log n) Alberto Montresor (UniTN) Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 52 / 52 Alberto Montresor (UniTN) 51 / 52 Merge Sort Capitolo 2 - Analisi di algoritmi 16 ottobre 2014 52 / 52
© Copyright 2025 ExpyDoc