Ülesandeks on kontrollida etteantud positiivse täisarvu jaoks, kas ta on 2 aste. Vaatleme järgmist algoritmi selle ülesande lahendamiseks. Kui arv on paarisarv, siis jagatakse ta 2-ga ja korratakse sama tegevust tulemuseks saadud arvuga. Kui nii tehes jäädakse lõpuks pidama arvul 1, siis tagastatakse „tõene”, vastasel korral aga tagastatakse „väär”. Milline on selle algoritmi halvima juhu keerukushinnang kujul Θ(f(n)), kus n on argumendiks saadud arvu numbrite arv kahendsüsteemis? Eeldada, et kõik jagamised on keerukusega Θ(1).

Algoritmi töökiiruse sõltuvust sisendi suurusest väljendab funktsioon T(n) = n(n+1). Millistesse keerukusklassidesse see kuulub?

Vali kõik sobivad vastused.

Definitsioon.

Olgu f ja g naturaalarvuliste argumentidega

funktsioonid. Siis f on O(g), kui leiduvad c > 0 ja N > 0 nii, et |f(n)| <

c|g(n)| iga n > N korral.

Olgu

• f(n) = 3n² + 12n - 2
• g(n) = n

Kas nende funktsioonide puhul kehtib lause „f on O(g)”?

Vali kõik

sobivad variandid.

Definitsioon.

Olgu f ja g naturaalarvuliste argumentidega

funktsioonid. Siis f on O(g), kui leiduvad c > 0 ja N > 0 nii, et

|f(n)| < c|g(n)| iga n > N korral.

Olgu

• f(n) = 5n + 5
• g(n) = n

Kas nende funktsioonide puhul kehtib lause „f on O(g)”?

Vali kõik

sobivad variandid.

Vaatleme algoritmi, mis liidab sisendiks saadud naturaalarvu n iseendale ja väljastab tulemuse. Milline on selle algoritmi keerukus kujul Θ(f(n)), eeldusel et arvud esitatakse tavakujul (st kümnendsüsteemis) ja liitmine toimub vastavalt tavaalgoritmile?

Mille prindib järgmine funktsioon sisendil "INFORMATSIOON"?

def tag(sõne):
    if len(sõne) == 0:
        return
    print(sõne[0], end=' ')
    tag(sõne[1:])

Mis keerukusega on järgnev algoritm?

def seljakott(a, k):
    if len(a) == 0 or k <= 0:
        return []
    a0 = [a[0]] + seljakott(a[1:], k-a[0])
    a1 = seljakott(a[1:], k)
    s0 = sum(a0)
    s1 = sum(a1)
    if s0 > k or s1 > s0:
        return a1
    return a0

Meil on arvuti, millega võtab 10 miljoni elemendilise järjendi sorteerimine pistemeetodiga aega keskmiselt 512000 sekundit. Umbes mitu sekundit võtab aega 100 tuhande elemendilise järjendi sorteerimine sama meetodiga samal arvutil?

def permutatsioon(sõne, perm=""):
    if len(sõne) == 0:
        print(perm)
    else:
        for i in range(len(sõne)):
            permutatsioon(sõne[:i] + sõne[i+1:], perm + sõne[i])

def bittvektorite_generaator(n, vektor = ""):
    if len(vektor) == n:
        return 1
    return bittvektorite_generaator(n, vektor + "0") + bittvektorite_generaator(n, vektor + "1")