Compiti sui tempi di esecuzione

27/05/2015

Si confrontino le seguenti funzioni utilizzando le relazioni O, Ω e Θ (giustificando le risposte):

f(n)	g(n)
10n3 + log n + 2n	n2 + log n5
n!	2n
2n	2n+100

Svolgimento

10n3 + log n + 2n

n2 + log n5

In questo caso è possibile considerare solo il grado più alto di entrambe le espressioni. Siccome n² + log n⁵ si può scrivere come n² + 5log n, il confronto è tra

f(n) = n³ e g(n) = n²

quindi f(n) = Ω(g(n))

n!

2n

In questo caso è opportuno iniziare a sviluppare le serie per capire quale cresce più velocemente.

n! = n * (n-1)! = n * (n-1) * (n-2)! eccetera

2ⁿ = 2 * 2^n-1 = 2 * 2 * 2^n-2 eccetera

per n = 0, n! = 1 (per definizione) e 2⁰ = 1

per n = 1, n! = 1 (per definizione) e 2¹ = 2

per n = 2, n! = 2 (per definizione) e 2² = 4

per n = 3, n! = 6 (per definizione) e 2³ = 8

per n = 4, n! = 24 (per definizione) e 2⁴ = 16

da questo punto in poi, ogni n contribuisce a moltiplicare n in n! e 2 in 2ⁿ

Quindi possiamo dire che per n₀ = 5 vale che f(n) = Ω(g(n))

2n

2n+100

Questo caso è semplicemente f(n) = Θ(g(n)) con c₁ = c₂ = 2¹⁰⁰

28/01/2015

Si risolvano le seguenti ricorrenze:

• T(n) = 3T(n/2) + n²
• T(n) = 4T(n/2) + n²
• T(n) = T(n/2) + 2ⁿ

Svolgimento

Si può utilizzare per tutti e tre i problemi il teorema master per la ricorsione:

n^log₂3 ≈ n^1,1 < n²

in questo problema f(n) =n², g(n) = n^1,1+ε, con 0 < ε < ∼0,9, quindi f(n) = Ω(g(n))

Rientriamo nel terzo caso, quindi dobbiamo accertarci che esista un c < 1 t.c. af(n/b) < cf(n), quindi 3(n/2)² = 3/4 n² < cn². Scegliendo un 3/4 < c < 1 si ha che cn² è sempre maggiore.

Perciò il costo è T(n) = Ω(f(n)) = Ω(n²)

Nel secondo problema n^log₂4 = n²
Rinetriamo nel terzo caso, quindi T(n) = Θ(n² ln n), poiché l'algoritmo deve eseguire n² operazioni per l'altezza dell'albero.

Nel terzo problema n^log₂1 = n⁰ = 1 < 2ⁿ
Quindi f(n) = 2ⁿ = Ω(1)

Siamo ancora nel terzo caso, si può dire che T(n) = Θ(2ⁿ) a patto che 2ⁿ/2 < c2ⁿ con 1/2 < c < 1.

23/01/2014

Si definiscano formalmente le relazioni O, Ω, Θ e, utilizzando le definizioni date e
nient’altro, si dimostri la verità o la falsità di ciascuna delle seguenti affermazioni:

1. n logn = Θ(n²)
2. n + √3n = Ω(logn)
3. 4n log n = Ο(4n + log n²)
4. 2n+k = Ο(2n ), dove k è una costante intera positiva
5. 2ⁿ⁺ⁿ = Ο(2ⁿ)

Svolgimento

Si dice f(n) = O(g(n)) se ∃ c > 0 tale che 0 ≤ cf(n) ≤ g(n)∀ n ≫ n₀

Si dice f(n) = Ω(g(n)) se ∃ c > 0 tale che 0 ≤ g(n) ≤ cf(n) ∀ n ≫ n₀

Si dice f(n) = Θ(g(n)) se ∃ c₁, c₂ > 0 tale che 0 ≤ c₁f(n) ≤ g(n) ≤ c₂f(n) ∀ n ≫ n₀

• n logn = Θ(n²)

f(n) = o(g(n)) perché 0 < n logn < cn² ⇒ 0 < logn < cn
che è sempre vera per n ≫ n₀

Quindi il primo problema è falso.

• n + √3n = Ω(logn)

Se il secondo problema è vero, esiste c > 0 tale che 0 ≤ log n ≤ c(n+√3n)

Si può scrivere come e^{log n} < e^c(n+√3n)
cioè n < e^cn(1+√3)
Evidentemente c può "assorbire" (1 + √3), basta trovare un c₁ = c + √3c; con c > 0 la crescita di e^cn è esponenziale, e quindi tende a essere più grande di n per valori grandi di n.

In alternativa, utilizzando il teorema per cui f(n) = Ω(g(n)) ⇒

$\underset{n\to \infty }{\lim }\frac{f\left(n\right)}{g\left(n\right)}=\mathrm{\infty }$

abbiamo che

$\underset{n\to \infty }{\lim }\frac{n+\mathrm{\surd 3}n}{log\mathrm{n}}\stackrel{H}{=}\underset{n\to \infty }{\lim }\frac{1+\mathrm{\surd 3}}{\frac{1}{\mathrm{n}}}=\underset{n\to \infty }{\lim }n+\mathrm{\surd 3}n=\infty$

quindi il secondo problema è vero.

• 4n log n = Ο(4n + log n²)

Il terzo problema è un confronto tra 4n logn e 4n + 2log n, che si può riscrivere, dividendo per 4n, come

log n = O(1 + (log n)/2n)

Per la definizione di O, il problema è vero se esiste c tale che c(log n) ≤ 1 + (log n)/2n

Semplificando ancora, dividendo per log n, si ottiene c ≤ 1/log n + 1/2n

Per n molto grande, 1/log n tende a zero, ma 1/2 n tende a infinito, mentre c è una costante. Di conseguenza il terzo problema è vero.

• 2n+k = Ο(2n), dove k è una costante intera positiva

Questo è vero se esiste c > 0 tale che c(2n+k) ≤ 2n. Scegliendo c < 1 si ha che quando h*c < 2n il problema è vero, e siccome h e c sono costanti, mentre 2n tende a infinito, il problema è vero.

• 2ⁿ⁺ⁿ = Ο(2ⁿ)

Riscrivendo il problema come 2ⁿ2ⁿ = Ο(2ⁿ), si ha che perché il problema sia vero deve essere che 0 ≤ 2ⁿ2ⁿ ≤ 2ⁿ, ma semplificando si ha 0 ≤ 2ⁿ ≤ 1, che è palesemente falso.