Esercizi svolti sulle ricorrenze

Algoritmi e Strutture Dati (Elementi)
Esercizi sulle ricorrenze
Proff. Paola Bonizzoni / Giancarlo Mauri / Claudio Zandron
Anno Accademico 2002/2003
Appunti scritti da Alberto Leporati e Rosalba Zizza
Esercizio 1
Posti T (0) = 1 e T (1) = 1, risolvere la seguente equazione di ricorrenza
utilizzando il metodo iterativo per determinare un limite asintotico superiore:
T (n) = 2 · T (n − 2) + 3
Facoltativo: determinare il limite asintotico stretto.
Soluzione. Applicando il metodo iterativo si ottiene:
T (n) = 2 · T (n − 2) + 3 = 2 · [2 · T (n − 4) + 3] + 3
= 22 · T (n − 4) + (2 · 3) + 3
= 22 · [2 · T (n − 6) + 3] + 2 · 3 + 3
= 23 · T (n − 6) + 22 · 3 + 2 · 3 + 3
Proseguendo in questo modo, per k fissato avremo:
T (n) = 2k · T (n − 2k) + 2k−1 · 3 + 2k−2 · 3 + . . . + 20 · 3
Se n è pari raggiungiamo il valore T (0) per k = n/2. Se n è dispari, raggiungiamo il valore T (1) per k = ⌊n/2⌋. Possiamo quindi trascurare questa
differenza, e assumere che n sia pari. La ricorrenza può allora essere scritta
come segue:
T (n) = 2
n/2
· T (0) + 3 ·
n/2
X
2i−1
i=1
(n/2)−1
= 2n/2 + 3 ·
=2
n/2
X
2i
i=0
(n/2)−1+1
+3· 2
= 4 · 2n/2 − 3
1
−1
Un limite asintotico superiore (non stretto) è T (n) = O(2n ).
Per quanto riguarda la parte facoltativa evidenziamo che 2n/2 6= Θ(2n ),
poiché 2n/2 6= Ω(2n ). Essendo però:
2n/2 = Ω(2n/2 )
e
2n/2 = O(2n/2)
segue che il limite asintotico stretto è:
T (n) = 4 · 2n/2 − 3 = Θ(2n/2 )
Esercizio 2
Posti T (0) = 1 e T (1) = 1, risolvere la seguente equazione di ricorrenza
utilizzando il metodo iterativo per determinare un limite asintotico superiore:
T (n) = 3 · T (n − 2) + 5
Facoltativo: determinare il limite asintotico stretto.
Soluzione. Applicando il metodo iterativo si ottiene:
T (n) = 3 · T (n − 2) + 5 = 3 · [3 · T (n − 4) + 5] + 5
= 32 · T (n − 4) + (3 · 5) + 3
= 32 · [3 · T (n − 6) + 5] + 3 · 5 + 3
= 33 · T (n − 6) + 32 · 5 + 3 · 5 + 3
Proseguendo in questo modo, per k fissato avremo:
T (n) = 3k · T (n − 2k) + 3k−1 · 5 + 3k−2 · 5 + . . . + 30 · 5
Se n è pari raggiungiamo il valore T (0) per k = n/2. Se n è dispari, raggiungiamo il valore T (1) per k = ⌊n/2⌋. Possiamo quindi trascurare questa
differenza, e assumere che n sia pari. La ricorrenza può allora essere scritta
2
come segue:
T (n) = 3
n/2
· T (0) + 5 ·
n/2
X
3i−1
i=1
(n/2)−1
= 3n/2 + 5 ·
X
3i
i=0
3(n/2)−1+1 − 1
= 3n/2 + 5 ·
3−1
5
7
= · 3n/2 −
2
2
Un limite asintotico superiore (non stretto) è T (n) = O(3n ).
Per quanto riguarda la parte facoltativa evidenziamo che 3n/2 6= Θ(3n ),
poiché 3n/2 6= Ω(3n ). Essendo però:
3n/2 = Ω(3n/2 )
e
3n/2 = O(3n/2)
segue che il limite asintotico stretto è:
T (n) =
7 n/2 5
· 3 − = Θ(3n/2 )
2
2
Esercizio 3
Risolvere esattamente la seguente equazione di ricorrenza, utilizzando il metodo iterativo.
(
2
se n = 1
T (n) =
n
8 · T ( 2 ) + n se n > 1
Specificare poi un limite asintotico superiore.
Suggerimento: ricordiamo che alogb n = nlogb a .
3
Soluzione. Applicando il metodo iterativo si ottiene:
n
T (n) = 8 · T
+n
2 h
n
ni
=8 8·T 2 +
+n
2
n2
n
= 82 · T 2 + 8 · + n
2 2 i
h
n
n
n
2
=8 8·T 3 + 2 +8· +n
2
2
n 2
n
n
3
2
=8 ·T 3 +8 · 2 +8· +n
2
2
2
Proseguendo in questo modo, per k fissato avremo:
k−1 i
n X
8
k
T (n) = 8 · T k +
·n
2
2
i=0
Il valore T (1) viene raggiunto quando 2nk = 1, ovvero quando k = log2 n.
La ricorrenza può pertanto essere scritta come:
(log2 n)−1 i
8
T (n) = 8
· T (1) +
·n
2
i=0
(log2 n)−1 i
X
8
log2 8
=n
· T (1) + n
2
i=0
X
log2 n
(log2 n)−1
4log2 n − 1
3
i=0
n
n
= 2n3 + (nlog2 4 − 1) = 2n3 + (n2 − 1)
3
3
3
3
n
n
7n
n
= 2n3 +
− =
− = O(n3)
3
3
3
3
3
= 2n + n
X
4i = 2n3 + n ·
Esercizio 4
Determinare la forma esplicita (detta anche forma chiusa) della seguente
relazione di ricorrenza:
(
4 · T (n − 1) − 21 se n ≥ 1
T (n) =
12
se n = 0
4
Soluzione. Applicando il metodo iterativo si ottiene:
T (n) = 4 · T (n − 1) − 21
= 4 · [4 · T (n − 2) − 21] − 21
= 42 · T (n − 2) − 4 · 21 − 21
= 42 · [4 · T (n − 3) − 21] − 4 · 21 − 21
= 43 · T (n − 3) − 42 · 21 − 4 · 21 − 21
= ...
i
= 4 · T (n − i) − 21 ·
i−1
X
4k
k=0
La condizione base T (0) = 12 viene applicata quando n − i = 0, ovvero
quando i = n. Otteniamo quindi:
n
T (n) = 4 · T (0) − 21 ·
n−1
X
4k
k=0
n
4 −1
4−1
= 4n · 12 − 7 · (4n − 1)
= 4n · 12 − 4n · 7 + 7
= 5 · 4n + 7
= 4n · 12 − 21 ·
Esercizio 5
Risolvere la seguente ricorrenza:
(
T n2 + log2 n se n ≥ 2
T (n) =
Θ(1)
se n = 1
5
Soluzione. Applicando il metodo iterativo si ottiene:
n
T (n) = T
+ log2 n
2
n
n
=T
+ log2 + log2 n
2
4n n
= T 2 + log2 + log2 n
2
2n n
n
= T 3 + log2 2 + log2 + log2 n
2
2
2
= ...
n
n
n
= T i + log2 i−1 + . . . + log2 + log2 n
2
2
2
i−1
n
n X
log2 k
=T i +
2
2
k=0
La condizione base si applica quando 2ni = 1, ovvero quando i = log2 n.
Ricordando che log2 2ni = log2 n − log2 2i = log2 n − i, otteniamo:
log2 n−1
T (n) =
log2
+T
X
log2
n
+ Θ(1)
X
(log2 n − k) + Θ(1)
X
log2 n −
k=0
log2 n−1
=
k=0
log2 n−1
=
2k
2k
k=0
log2 n−1
=
n
n
X
2i
log2 n−1
k=0
X
k + Θ(1)
k=0
Pm
Ricordiamo che k=1 k è la serie aritmetica, per la quale risulta
1
m(m + 1). Dunque:
2
(log2 n − 1) log2 n
+ Θ(1)
2
1
1
= log22 n − log22 n + log2 n + Θ(1)
2
2
2
= Θ(log2 n)
T (n) = (log2 n) (log2 n) −
6
Pm
k=1 k
=
Esercizio 6
Dimostrare che T (n) = O(log2 n), dove
(
T ⌊ n2 ⌋ + 1 se n ≥ 2
T (n) =
1
se n = 1
utilizzando sia il metodo iterativo che il metodo per sostituzione.
Soluzione.
• Metodo iterativo. Per il momento poniamo, per semplicità, n = 2k .
Si ottiene:
n
n
T (n) = T
+1=T 2 +1+1
2
2n =T 3 +1+1+1
2
= ...
n
=T i +i
2
La condizione base T (1) = 1 si applica quando
i = log2 n. Si ottiene allora:
n
2i
= 1, ovvero quando
T (n) = 1 + log2 n = O(log2 n)
Se invece assumiamo n 6= 2k , poiché n = 2log2 n ≤ 2⌈log2 n⌉ , riapplicando
lo stesso procedimento otteniamo:
T (n) = T (2log2 n ) ≤ T 2⌈log2 n⌉ = 1 + log2 2⌈log2 n⌉
= 1 + ⌈log2 n⌉ < 2 + log2 n = O(log2 n)
• Metodo per sostituzione. Dimostriamo che vale T (n) = O(log2 n)
per induzione su n, con n ≥ 2.
Base dell’induzione. Per n = 2 vale T (2) = O(log2 2) = O(1).
Passo di induzione. Supponiamo che l’uguaglianza valga fino a n − 1,
e dimostriamo che vale anche per n. Vale:
n
T (n) = T
+1
2
7
Per ipotesi induttiva vale T n2 = O(log2 n2 ); per definizione, questo
significa che esistono c > 0 (reale) e n0 ∈ N tali che, per ogni n > n0 ,
vale:
n
n
T (n) = T
+ 1 ≤ c · log2 + 1
2
2
Si tratta allora di dimostrare che esiste c > 0 tale che:
c · log2
n
+ 1 ≤ c · log2 n
2
Poiché vale:
n
n
c · log2 + 1 ≤ c · log2 n ⇐⇒ c log2 − log2 n ≤ −1
2
2
n
⇐⇒ c log2 2 ≤ −1
n
1
≤ −1
⇐⇒ c log2
2
⇐⇒ c (−1) ≤ −1
⇐⇒ c ≥ 1
basta scegliere c ≥ 1.
Similmente, se n 6= 2k , poiché vale n = 2log2 n ≤ 2⌈log2 n⌉ , riapplicando
il medesimo procedimento otteniamo:
T (n) = T 2log2 n ≤ T 2⌈log2 n⌉ ≤
≤ c · log2 2⌈log2 n⌉ ≤ c · log2 2log2 n+1 = c (log2 n + 1)
e si può facilmente dimostrare che esiste c > 0 tale che T (n) = O(log2 n).
Esercizio 7
Risolvere la seguente ricorrenza:
(
4 · T ⌊ n2 ⌋ + n se n ≥ 2
T (n) =
1
se n = 1
8
Soluzione. Applicando il metodo iterativo, otteniamo:
j n k
T (n) = 4 · T
+n
2 k j ki
h
j
n
n
=4 4·T
+
+n
j n 4k
j2n k
= 42 · T
+4
+n
22
2
= ...
i−1
jnk
j n k X
k
i
=4 ·T
+
4
2i
2k
k=0
La condizione base si applica quando:
jnk
=1
2i
ovvero quando:
n
1< i ≤2
2
cioè quando:
2i < n ≤ 2i+1
ovvero quando:
i = ⌊log2 n⌋
Allora otteniamo:
⌊log2 n⌋−1
T (n) = 4
⌊log2 n⌋
+
X
4
k
k=0
jnk
2k
⌊log2 n⌋−1
2 log2 n
≤ (2 )
2 log2 n
+n
X
2k = (2)2 log2 n + n ·
k=0
log2 n
2⌊log2 n⌋ − 1
2−1
2
≤ (2)
+ n (2
− 1) = 2log2 n + n (n − 1)
= n2 + n2 − n = O(n2 )
Esercizio 8
Risolvere la seguente equazione di ricorrenza con il metodo iterativo:
(
T (n − 1) + log2 n se n ≥ 2
T (n) =
Θ(1)
se n = 1
9
Soluzione.
T (n) = T (n − 1) + log2 n =
= T (n − 2) + log2 (n − 1) + log2 n =
= ...
= T (n − i) +
i−1
X
log2 (n − k)
k=0
La condizione base si applica quando n − i = 1, ovvero quando i = n − 1.
Allora possiamo scrivere:
T (n) =
n−2
X
log2 (n − k) + Θ(1)
k=0
Resta quindi da valutare la sommatoria. Osserviamo anzitutto che, essendo
il logaritmo una funzione crescente, posso maggiorare la sommatoria come
segue:
n−2
X
log2 (n − k) ≤ (n − 1) log2 n
k=0
e quindi T (n) = O(n log2 n). D’altra parte, per determinare un limite inferiore al valore della sommatoria possiamo spezzarla in due parti e trascurare
la seconda parte, come segue:
n−2
X
⌊ n−2
⌋
2
log2 (n − k) =
X
k=0
k=0
≥
log2 (n − k) ≥
k=0
=
log2 (n − k)
k=⌊ n−2
⌋+1
2
⌊ n−2
⌋
2
X
n−2
X
log2 (n − k) +
n−2
2
log2
e quindi T (n) = Ω(n log2 n).
10
n+2
2
n−2
n−2
log2 n −
2
2
Esercizio 9
Risolvere la seguente equazione di ricorrenza con il metodo della sostituzione:
(
T ⌊ n2 ⌋ + T ⌊ 2n
⌋
+ Θ(n2 ) se n ≥ 1
3
T (n) =
Θ(1)
se n = 0
Soluzione. Dalla definizione di T (n) vediamo subito che vale sicuramente T (n) = Ω(n2 ). Dimostriamo che vale anche T (n) = O(n2 ), ovvero che
esistono c > 0 (reale) e n0 ∈ N tali che, per ogni n > n0 , vale T (n) ≤ c · n2 .
Anzitutto osserviamo che il termine Θ(n2 ) indica una funzione g(n) per
la quale esistono una costante reale d > 0 e un intero n1 ∈ N tali che per ogni
n > n1 vale g(n) ≤ d · n2 . Senza perdere in generalità possiamo supporre che
sia n1 < n0 ; infatti, nel caso in cui ciò non valga saremmo ancora in grado di
dimostrare che T (n) = O(n2 ) poiché sarebbe T (n) ≤ c · n2 per ogni n > n1 ,
con c ed n1 fissati.
La dimostrazione procede per induzione su n.
Base dell’induzione. Se n = 0 l’asserto è vero, poiché una quantità che è Θ(1)
è limitata superiormente da una costante, e quindi è sicuramente O(n2 ).
Passo di induzione. Supponiamo che l’asserto valga per ogni i < n, e
dimostriamo che vale anche per n. Poiché n ≥ 1, possiamo scrivere:
j n k
2n
+ Θ(n2 )
+T
T (n) = T
2
3
Per ipotesi induttiva, per ogni n > n0 valgono:
2
j n k2
j n k
2n
2n
T
≤c
e
T
≤c
2
2
3
3
D’altra parte, abbiamo visto che per ogni n > n0 (> n1 ) il termine Θ(n2 ) è
maggiorabile con d · n2 . Quindi:
2
j n k2
2n
T (n) ≤ c
+c
+ d n2
2
3
n2
4
≤c·
+ c · n2 + d n2
4
9
11
A questo punto imponiamo T (n) ≤ c · n2 e ricaviamo un vincolo sui possibili
valori di c. Vale:
4
n2
c·
+ c · n2 + d n2 ≤ c n2
4
9
se e solo se
4
1
c· +c· +d≤c
4
9
se e solo se
36
c≥
d
11
Possiamo quindi concludere che se c ≥ 36
d vale T (n) ≤ c·n2 per ogni n > n0 ,
11
2
cioè che T (n) = O(n ).
Esercizio 10
Risolvere la seguente equazione di ricorrenza con il metodo della sostituzione:
(
T ⌊ n2 ⌋ + 2 · T ⌊ n4 ⌋ + Θ(n) se n ≥ 2
T (n) =
Θ(1)
se n = 1
Soluzione. Dalla definizione di T (n) vediamo subito che vale sicuramente
T (n) = Ω(n). Proviamo ora a dimostrare che vale anche T (n) = O(n),
ovvero che esistono c > 0 (reale) e n0 ∈ N tali che, per ogni n > n0 , vale
T (n) ≤ c · n.
Anzitutto osserviamo che il termine Θ(n) indica una funzione g(n) per la
quale esistono una costante reale d > 0 e un intero n1 ∈ N tali che per ogni
n > n1 vale g(n) ≤ d · n. Senza perdere in generalità possiamo supporre che
sia n1 < n0 ; infatti, nel caso in cui ciò non valga, siamo ancora in grado di
dimostrare che T (n) = O(n) poiché T (n) ≤ c · n per ogni n > n1 , con c ed
n1 fissati.
La dimostrazione procede per induzione su n.
Base dell’induzione. Se n = 1 l’asserto è vero, poiché una quantità che è
Θ(1) è limitata superiormente da una costante, e quindi è sicuramente O(n).
Passo di induzione. Supponiamo che l’asserto valga per ogni i < n, e
dimostriamo che vale anche per n. Poiché n ≥ 2, possiamo scrivere:
j n k
j n k
T (n) = T
+2·T
+ Θ(n)
2
4
12
Per ipotesi induttiva, per ogni n > n0 valgono:
jnk
j n k
jnk
j n k
T
≤c
e
T
≤c
2
2
4
4
D’altra parte, abbiamo visto che per ogni n > n0 (> n1 ) il termine Θ(n) è
maggiorabile con d · n. Quindi:
jnk
jnk
T (n) ≤ c
+2c
+d·n
2
4
n
n
≤ c· + 2c· +dn = cn+dn
2
4
A questo punto, se imponiamo T (n) ≤ c n otteniamo:
cn+dn ≤ cn
se e solo se
d≤0
che è chiaramente impossibile. Dunque risulta che T (n) 6= O(n).
Proviamo allora a dimostrare che T (n) = O(n log2 n), ovvero che esistono
c > 0 (reale) e n0 ∈ N tali che per ogni n > n0 vale T (n) ≤ c · n. Come
prima, siano d > 0 e n1 ∈ N una costante reale e un intero tali che per ogni
n > n1 vale Θ(n) ≤ d · n. Inoltre, assumiamo ancora che sia n1 < n0 .
La dimostrazione procede per induzione su n.
Base dell’induzione. Se n = 1 l’asserto è vero, poiché una quantità che è Θ(1)
è limitata superiormente da una costante, e quindi è sicuramente O(n log2 n).
Passo di induzione. Supponiamo che l’asserto valga per ogni i < n, e
dimostriamo che vale anche per n. Poiché n ≥ 2, possiamo scrivere:
j n k
j n k
T (n) = T
+2·T
+ Θ(n)
2
4
Per ipotesi induttiva, per ogni n > n0 valgono:
j n k
jnk
jnk
j n k
jnk
jnk
T
≤c
log2
e
T
≤c
log2
2
2
2
4
4
4
D’altra parte, abbiamo visto che per ogni n > n0 (> n1 ) vale Θ(n) ≤ d · n.
Quindi:
jnk
jnk
jnk
jnk
T (n) ≤ c
log2
+2c
log2
+d·n
2
2
4
4
n
n
n
n
≤ c · log2 + 2 c · log2 + d n
2
2
4
4
13
Ora imponiamo T (n) ≤ c · n log2 n e ricaviamo un vincolo sui possibili valori
di c. Vale:
n
n
n
n
c · log2 + 2 c · log2 + d n ≤ c · n log2 n
2
2
4
4
se e solo se:
1
n
1
n
c · log2 + 2 c · log2 + d ≤ c · log2 n
2
2
4
4
se e solo se:
n
n
2 c log2 + 2 c log2 + 4 d ≤ 4 c log2 n
2
4
se e solo se:
2 c (log2 n − 1) + 2 c (log2 n − 2) + 4 d ≤ 4 c log2 n
se e solo se:
−2 c − 2 c + 4 d ≤ 0
se e solo se:
2
d
3
Possiamo quindi concludere che se c ≥ 23 d vale T (n) ≤ c · n log2 n per ogni
n > n0 , cioè che T (n) = O(n log2 n).
Purtroppo ciò non basta per concludere che T (n) = Θ(n log2 n), dato che
all’inizio dell’esercizio abbiamo dimostrato solamente che T (n) = Ω(n). Mostriamo allora che T (n) = Ω(n log2 n). Poiché nell’espressione di T (n) compare un termine in n4 , risulterà più comodo dimostrare che T (n) = Ω(n log4 n).
Osserviamo che ciò equivale a dimostrare che T (n) = Ω(n log2 n), poiché:
n
log2 n
=Ω
log2 n
Ω(n log4 n) = Ω n
log2 4
2
c≥
ed essendo la notazione Ω invariante rispetto alla moltiplicazione per costanti
possiamo concludere che Ω(n log4 n) = Ω(n log2 n).
Per dimostrare che T (n) = Ω(n log4 n) dobbiamo mostrare che esistono
una costante reale c > 0 e un intero n0 tali che:
∀ n > n0
T (n) ≥ c · n log4 n
Poniamo n0 = 1 e procediamo per induzione su n.
Base dell’induzione. Se n = 1 l’asserto è vero, poiché T (1) = Θ(1) ≥ c·0 = 0.
(T (1) non può essere negativo, dato che è il tempo impiegato da un certo
algoritmo su un’istanza di dimensione 1).
14
Passo di induzione. Supponiamo che la proposizione sia vera per ogni i < n,
e dimostriamo che vale anche per n. Consideriamo due casi, a seconda che n
sia oppure no una potenza di 4.
Se n = 4t (cioè n è una potenza di 4), allora la ricorrenza diventa:
n
n
T (n) = T
+2T
+ Θ(n)
2
4
Assumiamo che d > 0 sia una costante tale che, per ogni n > n0 , il termine
Θ(n) è maggiorabile da d · n. Per ipotesi induttiva, per ogni n > n0 valgono:
n
n
n
T
≥ c · log4
2
2
2
e
T
Quindi,
n
4
≥c·
n
n
log4
4
4
n
n
n
n
log4 + 2 c · log4 + d n
2
2
4
4
Imponendo T (n) ≥ c · n log4 n otteniamo:
T (n) ≥ c ·
c·
n
n
n
n
log4 + 2 c · log4 + d n ≥ c n log4 n
2
2
4
4
se e solo se
c
c
(log4 n − log4 2) + (log4 n − 1) + d ≥ c log4 n
2
2
se e solo se
−
c
c
log4 2 − + d ≥ 0
2
2
se e solo se
c
c
(log4 2 + 1) = (log4 2 + log4 4)
2
2
c
3
3
1
3
= log4 8 = c log4 2 = c
= c
2
2
2 log2 4
4
d≥
Pertanto, se c ≤ 34 d vale T (n) ≥ c n log4 n.
Se invece n 6= 4t (cioè se n non è una potenza di 4), osserviamo che:
n = 4log4 n ≥ 4⌊log4 n⌋
15
Sfruttando il fatto che ⌊x⌋ > x − 1, risulta:
T (n) = T 4log4 n ≥ T 4⌊log4 n⌋
≥ (abbiamo una potenza di 4)
≥ 4⌊log4 n⌋ log4 4⌊log4 n⌋
≥ 4log4 n−1 (log4 n − 1)
n
= (log4 n − 1)
4
Per n grande possiamo trascurare il termine −1, e approssimare T (n) come:
T (n) ≈
n
log4 n
4
che è chiaramente Θ(n log4 n), e quindi in particolare Ω(n log4 n).
16