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 n2 + log n5 si può scrivere come n2 + 5log n, il confronto è tra

f(n) = n3 e g(n) = n2

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

2n = 2 * 2n-1 = 2 * 2 * 2n-2 eccetera

per n = 0, n! = 1 (per definizione) e 20 = 1

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

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

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

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

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

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

2n 2n+100

Questo caso è semplicemente f(n) = Θ(g(n)) con c1 = c2 = 2100

28/01/2015

Si risolvano le seguenti ricorrenze:

  • T(n) = 3T(n/2) + n2
  • T(n) = 4T(n/2) + n2
  • T(n) = T(n/2) + 2n
Svolgimento

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

nlog23 ≈ n1,1 < n2

in questo problema f(n) =n2, g(n) = n1,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)2 = 3/4 n2 < cn2. Scegliendo un 3/4 < c < 1 si ha che cn2 è sempre maggiore.

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

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

Nel terzo problema nlog21 = n0 = 1 < 2n
Quindi f(n) = 2n = Ω(1)

Siamo ancora nel terzo caso, si può dire che T(n) = Θ(2n) a patto che 2n/2 < c2n 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 = Θ(n2)
  2. n + √3n = Ω(logn)
  3. 4n log n = Ο(4n + log n2)
  4. 2n+k = Ο(2n ), dove k è una costante intera positiva
  5. 2n+n = Ο(2n)
Svolgimento

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

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

Si dice f(n) = Θ(g(n)) se ∃ c1, c2 > 0 tale che 0 ≤ c1f(n) ≤ g(n) ≤ c2f(n) ∀ n ≫ n0

  • n logn = Θ(n2)

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

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 elog n < ec(n+√3n)
cioè n < ecn(1+√3)
Evidentemente c può "assorbire" (1 + √3), basta trovare un c1 = c + √3c; con c > 0 la crescita di ecn è 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)) ⇒

limnfngn=

abbiamo che

limnn+√3nlogn=Hlimn1+√31n=limnn+√3n=

quindi il secondo problema è vero.

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

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.

  • 2n+n = Ο(2n)

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