3
Dana je funkcija KumulativneVsote(t)
, ki dobi kot parameter tabelo celih števil t
in vrne novo tabelo s
, v kateri je vsak člen vsota prvih nekaj členov tabele t
: za vsak indeks k
je s[k] = t[0] + t[1] + ... + t[k]
.
(a) Preizkusi to funkcijo na nekaj primerih tabel t
in se prepričaj, da res deluje.
(b) Kakšna je časovna zahtevnost v odvisnosti od n (dolžine tabele t
)?
(c) Predelaj funkcijo tako, da bo vračala enake rezultate kot prej, njena časovna zahtevnost pa bo samo O(n).
4
(a) Napiši funkcijo Najmanjsi(t)
, ki kot parameter dobi tabelo celih števil t
in izpiše najmanjši element te tabele. Pri tem ne uporabljaj že obstoječih pythonovih funkcij, kot sta min
in max
.
(b) Število elementov v tabeli t
označimo z n. Kakšna je časovna zahtevnost te funkcije v odvisnosti od n? Kolikokrat mora tvoja funkcija primerjati po dva elementa tabele t
med seboj (z operatorji, kot so <
, >
, <=
in >=
)?
(c) Svojo funkcijo dopolni tako, da izpiše najmanjši in največji element tabele t
. Koliko primerjav izvede zdaj (v odvisnosti od n)?
(d) *Reši nalogo (c) tako, da na tabeli dolžine n izvede največ 3n/2 primerjav med elementi tabele. (Namig: če se tabela podaljša za 2 elementa, koliko dodatnih primerjav potrebuješ, da izračunaš novi minimum in maksimum?)