A2. Complessità degli Algoritmipages.di.unipi.it/bodei/CORSO_FP_20/FP/Lezioni/IntroAlgo... ·...
Transcript of A2. Complessità degli Algoritmipages.di.unipi.it/bodei/CORSO_FP_20/FP/Lezioni/IntroAlgo... ·...
Chiara Bodei, Jacopo SoldaniDipartimento di InformaticaUniversità of Pisa
A2. Complessità degli AlgoritmiFondamenti di Programmazione e Laboratorio
Notazione Asintotica
2
Sia 𝑓(𝑛) la funzione che descrive la complessità in tempo/spazio di un algoritmo su input didimensione 𝑛, es
𝑇(𝑛) = 3𝑛2 + 14𝑛 + 2 e 𝑆(𝑛) = 34𝑛 + 12
La notazione asintotica permette di astrarre da dettagli influenti (come costantimoltiplicative, termini di ordine inferiore e costanti), concentrandosi sull’ordine di grandezzadeterminato da 𝑓(𝑛) stesso, es
𝑇(𝑛) = 𝑂(𝑛2) e 𝑆(𝑛) = 𝑂(𝑛)
Notazione Asintotica: 𝑂
3
𝑓(𝑛) = 𝑂(𝑔(𝑛)) se ∃𝑛0 > 0, 𝑐 > 0: ∀𝑛 > 𝑛0 . 𝑓 𝑛 ≤ 𝑐 ∙ 𝑔(𝑛)
NB: 𝑂 consente di definire upper bound (limiti superiori) per la complessità di un algoritmo,ovvero per dire che "si spende al massimo quell’ordine di grandezza di costo…"
Notazione Asintotica: 𝛀
4
𝑓(𝑛) = Ω(𝑔(𝑛)) se ∃𝑛0 > 0, 𝑐 > 0: ∀𝑛 > 𝑛0 . 𝑓 𝑛 ≥ 𝑐 ∙ 𝑔(𝑛)
NB: Ω consente di definire lower bound (limiti inferiori) per la complessità di un algoritmo,ovvero per dire che "si spende almeno quell’ordine di grandezza di costo…"
Notazione Asintotica: 𝛩
5
𝑓(𝑛) = 𝛩(𝑔(𝑛)) se ∃𝑛0 > 0, 𝑐1 > 0, 𝑐2 > 0: ∀𝑛 > 𝑛0 . 𝑐1 ∙ 𝑔 𝑛 ≤ 𝑓 𝑛 ≤ 𝑐2 ∙ 𝑔(𝑛)
NB: 𝛩 indica che la complessità di un algoritmo cresce quanto una certa funzione 𝑔(𝑛),ovvero per dire che "si spende esattamente quell’ordine di grandezza di costo…"
Notazione Asintotica: Proprietà
6
𝑂 definisce upper bound, Ω definisce lower bound, quindi…
Proprietà
Date due funzioni 𝑓(𝑛) e 𝑔(𝑛)
𝑓(𝑛) = 𝛩 𝑔 𝑛
se e solo se
𝑓 𝑛 = 𝑂 𝑔 𝑛 ∧ 𝑓(𝑛) = Ω 𝑔 𝑛
La complessità di un algoritmo quindi cresce come 𝛩 𝑔 𝑛
se valgono i limiti superiore 𝑂 𝑔 𝑛 e inferiore Ω 𝑔 𝑛
Esempio
7
Consideriamo la seguente funzione
𝑓 𝑛 = 2n2 + n + 5
Vale quanto segue
A) 𝑓 𝑛 = 𝑂(𝑛2) // basta scegliere 𝑐 = 3 e 𝑛 = 3
B) 𝑓(𝑛) = Ω(𝑛2) // basta scegliere 𝑐 = 1 e 𝑛 = 0
C) 𝑓(𝑛) = 𝛩(𝑛2) // poiché valgono A e B
D) 𝑓(𝑛) = 𝑂 𝑛3 // basta scegliere 𝑐 = 2 e 𝑛 = 2
Mentre non vale che
E) 𝑓(𝑛) = Ω(𝑛3) // per nessuna coppia 𝑐, 𝑛
F) 𝑓(𝑛) = 𝛩(𝑛3) // poiché non vale E
Quando e Come Usare la Notazione Asintotica
8
Useremo 𝑂 𝑔 𝑛 per indicare che la complessità in tempo/spazio di un algoritmo è limitata superiormente dalla funzione 𝑔(𝑛)
→ L’ordine di grandezza del "costo massimo" necessario a risolvere un problema con un dato algoritmo è lo stesso della funzione 𝑓(𝑛)
Useremo Ω(ℎ(𝑛)) per indicare che la complessità di un problema è limitata inferiormente dalla funzione ℎ(𝑛)
→ L’ordine di grandezza del "costo minimo" necessario a risolvere un problema con un qualunque algoritmo è lo stesso della funzione 𝑔(𝑛)
Sia P un problema la cui complessità in tempo/spazio è Ω(𝑓(𝑛))
Un algoritmo è ottimo per P se la sua complessità in tempo/spazio è 𝑂 𝑓 𝑛
Analizzare la Complessità in Tempo/SpazioTre Casi
9
Algoritmo di Riferimento: RicercaSequenziale
10
Algoritmo per la ricerca di un intero x in un array A non ordinato
int ricercaSequenziale(int x, int A[], int lunghezza) {
for(int i=0;i<lunghezza;i++)
if(V[i]==x) return i;
return -1;
}
Qual è la complessità in tempo di ricercaSequenziale?
Determinare la Complessità di un Algoritmo
11
Osservazione: La complessità in tempo dell’algoritmo è determinata dal ciclo for che confronta gli elementi di A con l’elemento x ricercato
• Quanti confronti dobbiamo fare per trovare x in A?
… dipende da dove si trova x in A: all’inizio? Alla fine? Non c’è?
• Ovviamente cerchiamo una risposta che non sia "dipende (da dove si trova x)"
Qual è la complessità in tempo di ricercaSequenziale?
Tre Casi da Considerare (Sempre)
12
Nell’analisi della complessità in tempo/spazio di un algoritmo, si considerano le risorse (tempo di esecuzione/occupazione di memoria) usate dall’algoritmo stesso in funzione della dimensione 𝒏 dell’istanza del problema in ingresso
es. in RicercaSequenziale, 𝑛 è data dalla lunghezza dell’array A
A parità di dimensione, istanze diverse del problema potrebbero determinare consumi diversi di risorse di calcolo
es. in RicercaSequenziale, basta un confronto se x è il primo elemento di A
mentre servono n confronti se x è non è presente in A
→ Si distinguono tre casi: ottimo, pessimo, e medio
Caso Migliore
13
Supponiamo di denotare con 𝑡 𝑖 il tempo necessario ad eseguire un algoritmo su una singola istanza 𝑖 di un problema
Il tempo necessario ad un algoritmo per risolvere il caso migliore di unproblema (o caso ottimo) si determina come segue
𝑇𝑏𝑒𝑠𝑡 𝑛 = ministanze 𝑖 di dimensione 𝑛
𝑡 𝑖
𝑇𝑚𝑖𝑛 𝑛 denota quindi il tempo necessario a risolvere le istanze (di dimensione n) del problema che comportano meno lavoro per l’algoritmo
→ 𝑇𝑏𝑒𝑠𝑡 𝑛 purtroppo non fornisce molte informazioni sull’algoritmo
NB: Lo stesso ragionamento si applica per il calcolo dello spazio necessario nel caso migliore diun problema, ovvero 𝑆𝑏𝑒𝑠𝑡 𝑛
Analisi di RicercaSequenziale: Caso Migliore
14
Caso Migliore:
• x si trova nella prima posizione di A
• RicercaSequenziale termina dopo un solo confronto!
𝑇𝑏𝑒𝑠𝑡 𝑛 = 𝑂(1)
int ricercaSequenziale(int x, int A[], int lunghezza) {
for(int i=0;i<lunghezza;i++)
if(V[i]==x) return i;
return -1;
}
… effettivamente non otteniamo informazioni eccezionalmente interessanti sulla complessitàdi RicercaSequenziale
Caso Peggiore
15
Supponiamo di denotare con 𝑡 𝑖 il tempo necessario ad eseguire un algoritmo su una singola istanza 𝑖 di un problema
Il tempo necessario ad un algoritmo per risolvere il caso peggiore di unproblema (o caso pessimo) si determina come segue
𝑇𝑤𝑜𝑟𝑠𝑡 𝑛 = maxistanze 𝑖 di dimensione 𝑛
𝑡 𝑖
𝑇𝑤𝑜𝑟𝑠𝑡 𝑛 denota quindi il tempo necessario a risolvere le istanze (di dimensione n) del problema che comportano più lavoro per l’algoritmo
→ 𝑇𝑤𝑜𝑟𝑠𝑡 𝑛 quindi fornisce garanzie sulla prestazione dell’algoritmo
NB: Lo stesso ragionamento si applica per il calcolo dello spazio necessario nel caso pessimodi un problema, ovvero 𝑆𝑤𝑜𝑟𝑠𝑡 𝑛
Analisi di RicercaSequenziale: Caso Peggiore
16
Caso Peggiore:
• x non è presente in A
• RicercaSequenziale termina solo dopo aver confrontato x con tutti gli n elementi contenuti in A
𝑇𝑤𝑜𝑟𝑠𝑡 𝑛 = 𝑂(𝑛)
int ricercaSequenziale(int x, int A[], int lunghezza) {
for(int i=0;i<lunghezza;i++)
if(V[i]==x) return i;
return -1;
}
Quindi, nel peggiore dei casi, RicercaSequenziale richiede un numero di confronti linearenella dimensione dell’input (e mai in quantità maggiore)
Caso Medio
17
Supponiamo di denotare con 𝑡 𝑖 il tempo necessario ad eseguire un algoritmo su una singola istanza 𝑖 di un problema, e con 𝑃(𝑖) la probabilità di avere tale istanza in ingresso
Il tempo necessario ad un algoritmo per risolvere il caso medio di unproblema si determina come segue
𝑇𝑎𝑣𝑔 𝑛 = Σistanze 𝑖 di dimensione 𝑛
𝑃 𝑖 ∙ 𝑡 𝑖
𝑇𝑎𝑣𝑔 𝑛 denota quindi il tempo necessario a risolvere –in media– le istanze di dimensione n del problema considerato, ovvero le sue istanze "tipiche"
→ 𝑇𝑎𝑣𝑔 𝑛 approssima le prestazioni dell’algoritmo,
→ richiedendo però una distribuzione di probabilità dei possibili input
NB: Lo stesso ragionamento si applica per il calcolo dello spazio necessario nel caso medio diun problema, ovvero 𝑆𝑎𝑣𝑔 𝑛
Analisi di RicercaSequenziale: Caso Medio
18
Caso Medio: (richiede una conoscenza sulla distribuzione di probabilità dei possibili input)• Indichiamo con 𝑖𝑗 il caso in cui x si trova nella posizione 𝑗 di A• Supponiamo che x possa occupare ogni posizione di A con la medesima probabilità
• Abbiamo che 𝑃 𝑖𝑗 =1
𝑛e 𝑡 𝑖𝑗 ≈ 𝑗
• Ne segue che
𝑇𝑎𝑣𝑔 𝑛 ≈
1≤𝑗≤𝑛
1
𝑛∙ 𝑗 ≈
𝑛 + 1
2= 𝑂(𝑛)
int ricercaSequenziale(int x, int A[], int lunghezza) {
for(int i=0;i<lunghezza;i++)
if(V[i]==x) return i;
return -1;
}
RicercaSequenziale: Riepilogo
19
Caso Complessità in Tempo Complessità in Spazio
Migliore 𝑂 1 𝑂 𝑛
Peggiore 𝑂 𝑛 𝑂 𝑛
Medio 𝑂 𝑛 𝑂 𝑛
Serve sempre 𝑂(𝑛)spazio per memorizzare
gli elementi di A
RicercaSequenziale quindi è ottimo per il problema generale…
Lower Bound Tempo Lower Bound Spazio
Ω 1 Ω 𝑛
Ω 𝑛 Ω 𝑛
Ω 𝑛 Ω 𝑛
Problema della ricerca di un elemento in un array
…ma si può fare di meglio per casi più specifici :)
RicercaBinaria
20
Algoritmo per la ricerca di un intero x in un array A ordinato
int ricercaBinaria(int x, int A[], int lunghezza) {
int centro,sx,dx;
sx=0;
dx=lunghezza-1;
while(sx<=dx) {
centro = (sx+dx)/2;
if(A[centro]==x) return centro;
if(A[centro]>x) dx=centro-1;
else sx=centro+1;
}
return -1;
}
Analisi di RicercaBinaria
21
Caso Migliore
• L’elemento al centro di A è uguale a x
• 𝑇𝑏𝑒𝑠𝑡(𝑛) = 𝑂(1)
Caso Peggiore
• L’elemento x non è presente in A
• 𝑇𝑤𝑜𝑟𝑠𝑡 𝑛 = ?
Caso Medio
• Assumiamo che le istanze del problema siano equidistribuite
• 𝑇𝑎𝑣𝑔 𝑛 = ?
Provate, per esercizio, a calcolare 𝑇𝑤𝑜𝑟𝑠𝑡 𝑛 e 𝑇𝑎𝑣𝑔 𝑛 . Li calcoleremo comunque insieme perun’altra versione della RicercaBinaria… quella ricorsiva!
Analizzare Algoritmi RicorsiviTre Diversi Metodi
22
RicercaBinaria: Versione Ricorsiva
23
Algoritmo per la ricerca di un intero x in un array A ordinato
int ricercaBinaria(int x, int A[], int sx, int dx) {
if(sx>dx) return -1;
int centro = (sx+dx)/2;
if(A[centro]==x) return centro;
if(A[centro]>x) return ricercaBinaria(x,A,sx,centro-1);
else return ricercaBinaria(x,A,centro+1,dx);
}
Qual è la complessità in tempo di ricercaBinaria(nel caso peggiore)?
Analisi di RicercaBinaria
24
La complessità in tempo di RicercaBinaria rispetta la seguente relazione di ricorrenza
𝑇 𝑛 = ቐ𝑐 + 𝑇
𝑛
2𝑛 > 1
1 𝑛 = 1
NB: Esistono vari metodi per risolvere questo tipo di equazioni di ricorrenza..
int ricercaBinaria(int x, int A[], int sx, int dx) {
if(sx>dx) return -1;
int centro = (sx+dx)/2;
if(A[centro]==x) return centro;
if(A[centro]>x) return ricercaBinaria(x,A,sx,centro-1);
else return ricercaBinaria(x,A,centro+1,dx);
}
Metodo 1: Metodo dell’Iterazione
25
Idea: "Srotolare" la ricorsione nella relazione di ricorrenza, in modo da ottenere una sommatoria dipendente solo dalla dimensione 𝑛 del problema originale
Nel caso di RicercaBinaria, abbiamo che
𝑇 𝑛 = ቐ𝑐 + 𝑇
𝑛
2𝑛 > 1
1 𝑛 = 1
può essere "srotolata" come segue (assumendo che 𝑛 sia una potenza di 2)
𝑇 𝑛 = 𝑐 + 𝑇𝑛
2= 𝑐 + 𝑐 + 𝑇
𝑛
4= ⋯ = 𝑘 ∙ 𝑐 + 𝑇
𝑛
2𝑘
Metodo 1: Metodo dell’Iterazione (2)
26
Nel caso di RicercaBinaria, abbiamo che
𝑇 𝑛 = 𝑐 + 𝑇𝑛
2= 𝑐 + 𝑐 + 𝑇
𝑛
4= ⋯ = 𝑘 ∙ 𝑐 + 𝑇
𝑛
2𝑘
Dobbiamo continuare finché 𝑛
2𝑘= 1, ovvero fino a che 𝑘 = log2 𝑛
𝑇 𝑛 = log2 𝑛 ∙ 𝑐 + 𝑇 1 = 𝑐 log2 𝑛 + 1
Quindi, per RicercaBinaria, abbiamo che
𝑇(𝑛) = 𝑂(log 𝑛)
(al caso pessimo)
Analisi di RicercaBinaria
27
Caso Migliore
• L’elemento al centro di A è uguale a x
• 𝑇𝑏𝑒𝑠𝑡(𝑛) = 𝑂(1)
Caso Peggiore
• L’elemento x non è presente in A
• 𝑇𝑤𝑜𝑟𝑠𝑡 𝑛 = 𝑂(log 𝑛)
Caso Medio
• Assumiamo che le istanze del problema siano equidistribuite
• 𝑇𝑎𝑣𝑔 𝑛 = log 𝑛 − 1 +1
𝑛= 𝑂(log 𝑛)
𝑇𝑎𝑣𝑔 si può calcolare sempre con lo stesso approccio e sfruttando il fatto che le istanze delproblema siano equidistribuite
Metodo 2: Metodo della Sostituzione
28
Prendiamo, ad esempio, la seguente relazione di ricorrenza
𝑇 𝑛 = ቐ𝑇
𝑛
2+ 𝑛 𝑛 > 1
1 𝑛 = 1
e proviamo ad applicare il metodo della sostituzione
Idea: "Intuire" la soluzione della relazione di ricorrenza e utilizzare l’induzione matematica per dimostrare che la soluzione è quella intuita
Metodo 2: Metodo della Sostituzione (2)
29
𝑇 𝑛 = ቐ𝑇
𝑛
2+ 𝑛 𝑛 > 1
1 𝑛 = 1
Ipotesi: 𝑇 𝑛 = 𝑂 𝑛 , ovvero 𝑇 𝑛 ≤ 𝑐 ∙ 𝑛 (per un’opportuna costante 𝑐 > 0)
Dimostrazione:
Caso Base:
𝑇 1 = 1 ≤ 𝑐 ∙ 1 (vale per ogni 𝑐 > 0)
Passo Induttivo:
𝑇 𝑛 = 𝑇𝑛
2+ 𝑛 // per ipotesi induttiva 𝑇
𝑛
2≤ 𝑐 ∙
𝑛
2
≤ 𝑐 ∙𝑛
2+ 𝑛 =
𝑐
2+ 1 ∙ 𝑛
Quindi 𝑇 𝑛 ≤ 𝑐 ∙ 𝑛 per un qualunque 𝑐 ≥ 2 CVD
Digressione: Divide et Impera
30
La tecnica del divide et impera è una tecnica potente e generale utilizzabile per la progettazione di algoritmi e la risoluzione di problemi
Dato un problema di dimensione 𝑛:
• Il problema viene scomposto in 𝒔 sotto-problemi
• Ciascuno sotto-problema ha dimensione 𝒏
𝒅
• Suddividere il problema in sotto-problemi costa 𝒇 𝒏
Ne risultano relazioni di ricorrenza del tipo
𝑇 𝑛 = 𝑠 ∙ 𝑇𝑛
𝑑+ 𝑓 𝑛
Divide: Dividere i dati di ingresso in sottoinsiemi (o sotto-problemi)Impera: Risolvere ricorsivamente i sotto-problemi e combinare le
loro soluzioni per ottenere la soluzione globale
Digressione: Divide et Impera
31
La tecnica del divide et impera, quindi, permette di realizzare algoritmi ricorsivi per cui
𝑇 𝑛 = ቐ𝑠 ∙ 𝑇
𝑛
𝑑+ 𝑓 𝑛 𝑛 > 1
1 𝑛 = 1
RicercaBinaria
𝑇 𝑛 = ቐ𝑐 + 𝑇
𝑛
2𝑛 > 1
1 𝑛 = 1
Come risolvere (in generale) questo tipo di relazioni di ricorrenza?
Metodo 3: Master Theorem
32
Permette di determinare la soluzione di relazioni di ricorrenza in algoritmi basati su divide et impera, le cui relazioni di ricorrenza risultano essere del tipo
𝑇 𝑛 = ቐ𝑠 ∙ 𝑇
𝑛
𝑑+ 𝑓 𝑛 𝑛 > 1
1 𝑛 = 1
…vediamo come!
Verso il Master Theorem, Intuitivamente
33
Supponiamo che 𝑛 sia una potenza di 𝑑 e che la ricorsione si fermi quando 𝑛 = 1
L’albero di ricorsione è il seguente
𝑛
𝑛/𝑑 𝑛/𝑑 𝑛/𝑑
𝑛/𝑑2 𝑛/𝑑2 𝑛/𝑑2 𝑛/𝑑2 𝑛/𝑑2 𝑛/𝑑2…
…
…
𝑠
𝑠𝑠 𝑠
Verso il Master Theorem, Intuitivamente
34
Osservazione: I sotto-problemi al livello 𝑙 hanno dimensione 𝑛
𝑑𝑙. Quindi (escluso il tempo per
le chiamate ricorsive) il tempo speso al livello 𝑙 è 𝑓𝑛
𝑑𝑙
Osservazione: All’ultimo livello dell’albero di ricorsione abbiamo che 𝑛
𝑑𝑙= 1. Quindi l’albero di
ricorsione avrà al più altezza 𝑙 = log𝑑 𝑛
𝑛
𝑛/𝑑 𝑛/𝑑 𝑛/𝑑
𝑛/𝑑2 𝑛/𝑑2 𝑛/𝑑2 𝑛/𝑑2 𝑛/𝑑2 𝑛/𝑑2…
…
…
𝑠
𝑠𝑠 𝑠
Osservazione: Ogni nodo interno ha 𝑠 figli. Quindi al livello 𝑙 dell’albero di ricorsione ci sono 𝑠𝑙 nodi
…
Verso il Master Theorem, Intuitivamente
35
Osservazione: Ogni nodo interno ha 𝑠 figli. Quindi al livello 𝑙 dell’albero di ricorsione ci sono 𝑠𝑙 nodi
Osservazione: I sotto-problemi al livello 𝑙 hanno dimensione 𝑛
𝑑𝑙. Quindi (escluso il tempo per
le chiamate ricorsive) il tempo speso al livello 𝑙 è 𝑓𝑛
𝑑𝑙
Osservazione: All’ultimo livello dell’albero di ricorsione abbiamo che 𝑛
𝑑𝑙= 1. Quindi l’albero di
ricorsione avrà al più altezza 𝑙 = log𝑑 𝑛
La relazione di ricorrenza può essere quindi riscritta come segue:
𝑇 𝑛 =
𝑖=0
log𝑑 𝑛
𝑠𝑖𝑓𝑛
𝑑𝑖
La cui soluzione è data dal master theorem
Metodo 3: Master Theorem
36
𝑇 𝑛 = ቐ𝑠 ∙ 𝑇
𝑛
𝑑+ 𝑓 𝑛 𝑛 > 1
1 𝑛 = 1
ha soluzione
1) 𝑇(𝑛) = 𝛩 𝑛log𝑑 𝑠 se 𝑓(𝑛) = 𝑂(𝑛log𝑑 𝑠 − 𝜀) per 𝜀 > 0
2) 𝑇(𝑛) = 𝛩 𝑛log𝑑 𝑠 ∙ log 𝑛 se 𝑓(𝑛) = 𝛩(𝑛log𝑑 𝑠)
3) 𝑇(𝑛) = 𝛩 𝑓 𝑛 se 𝑓(𝑛) = Ω(𝑛log𝑑 𝑠+ 𝜀) per 𝜀 > 0 e 𝑠 ∙ 𝑓𝑛
𝑑≤ 𝑐 ∙ 𝑓 𝑛
per 𝑐 < 1 e 𝑛 sufficientemente grande
Jon Louis Bentley, Dorothea Haken, and James B. Saxe. 1980. A general method for solving divide-and-conquer recurrences. SIGACT News 12, 3 (Fall 1980), 36–44. DOI: https://doi.org/10.1145/1008861.1008865
Usare il Master Theorem
37
Nel caso di RicercaBinaria, abbiamo che
𝑇 𝑛 = 𝑇𝑛
2+ 𝑂(1)
Ovvero abbiamo che
𝑠 = 1, 𝑑 = 2 e 𝑓 𝑛 = 𝑂(1)
Visto che𝛩 𝑛log𝑑 𝑠 = 𝛩 𝑛log2 1 = 𝛩 𝑛0 = 𝛩(1)
siamo nel caso 2 del master theorem, e quindi
𝑇 𝑛 = 𝛩 𝑛log𝑑 𝑠 ∙ log 𝑛 = 𝛩 1 ∙ log 𝑛 = 𝛩 log 𝑛
Usare il Master Theorem
38
Esempio: Consideriamo la seguente relazione di ricorrenza
𝑇 𝑛 = 9 ∙ 𝑇𝑛
3+ 𝑛
Ovvero abbiamo che
𝑠 = 9, 𝑑 = 3 e 𝑓 𝑛 = 𝑛
Visto che𝛩 𝑛log𝑑 𝑠 = 𝛩 𝑛log3 9 = 𝛩 𝑛2
e che
𝑓 𝑛 = 𝑛 = 𝑂(𝑛2−𝜀) per 𝜀 = 1
siamo nel caso 1 del master theorem, e quindi
𝑇 𝑛 = 𝛩 𝑛log𝑑 𝑠 = 𝛩 𝑛log3 9 = 𝛩 𝑛2
Riepilogo
39
Quindi?
40
La notazione asintotica permette di esprimere la complessità in tempo/spazio di un algoritmo in modo compatto e sintetico, astraendo da dettagli non influenti (es. costanti)
Possiamo esprimere la complessità in tempo/spazio di un algoritmo in funzione delladimensione 𝒏 dell’istanza del problema in ingresso
Poiché, a parità di dimensione 𝑛, la complessità di un algoritmo può variare, è necessario analizzare l’algoritmo nel suo caso peggiore (e, se possibile, nel caso medio)
La complessità degli algoritmi ricorsivi si esprime agevolmente mediante relazioni di ricorrenza, che possono poi essere risolte applicando il metodo di iterazione, quello di sostituzione, o il master theorem