58053-7 Algoritmien suunnittelu ja analyysi (kev¨ at 2004) Harjoitus 1 (29.–30. tammikuuta)
1. J¨arjest¨a seuraavat funktiot kertaluokkiensa mukaiseen j¨arjestykseen:
n, logn, (logn)2, √
n(logn)2, (32)n,
√n, log logn, lognn, (13)n, 17 .
(T¨ass¨a ja jatkossa logn= log2n.)
2. Tarkastellaan algoritmejaA jaB, joiden aikavaatimuksille p¨ateeTA(n) = anα ja TB(n) = bβn joillakin vakioillaa, b, α >0,β >1. Oletetaan, ett¨a yhdess¨a aikayksik¨oss¨a kumpikin algoritmi pystyy k¨asittelem¨a¨an kokoa N olevia sy¨otteit¨a; siis N on vakio, jolle TA(N) = TB(N) = 1.
Kuinka suuria sy¨otteit¨a algoritmitAjaB pystyv¨at k¨asittelem¨a¨an 2 aikayksik¨oss¨a? (Ts. m¨a¨ar¨a¨a luvuistaN,αjaβ riippuvat luvutNA jaNB s.e.TA(NA) =TB(NB) = 2.)
3. Olkoong:N→R+ sellainen, ett¨a limn→∞g(n) =∞. Osoita, ett¨a funktiollaf:N→R+ p¨atee f =O(g) jos ja vain jos on olemassaa, b >0 joilla
f(n)≤ag(n) +b kaikillan.
4. Palautetaan mieleen kertomafunktio: n! = 1·2·3· · · · ·n. Osoita, ett¨a
log(n!) =
n
X
i=1
logi= Θ(nlogn) .
Vihje: Muodosta summalle yl¨araja termin lognavulla ja alaraja termin log(n/2) avulla.
5. Osoita, ett¨a
n
X
i=1
1
i = Θ(logn).
Vihje: k¨ayt¨a hyv¨aksi tietoa, ett¨a R
(1/x)dx= lnxja arvioi summaa sopivilla m¨a¨ar¨atyill¨a inte- graaleilla.
