Algoritmid ja andmestruktuurid (LTAT.03.005) Course Materials & Test Answers | moodle.ut.ee

// <![CDATA[

var ulObj = new Object();

ulObj.objektityyp = "programmidest";

ulObj.tyyp = "keskmise";

ulObj.keerukus = teeta() + "(n)";

ulObj.kasEeldused = true;

ulObj.eeldused = "jäägi leidmine ning arvude korrutamine, jagamine ja võrdlemine on keerukusega " + teeta() + "(1)"

document.write(hinnangule_vastav(ulObj));

// ]]>

Millised järgnevatest programmidest on keskmise ajalise keerukusega Θ(n)? Eeldada, et jäägi leidmine ning arvude korrutamine, jagamine ja võrdlemine on keerukusega Θ(1).

Märgi kõik sobivad vastused.

// <![CDATA[

document.write(astenda_lihtne_rek());

// ]]>

def astenda_lihtne_rek(a, n):
    if n == 0:
        return 1
    return a * astenda_lihtne_rek(a, n-1)

// <![CDATA[

document.write(astenda_kahend_rek1());

// ]]>

def astenda_kahend_rek1(a, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return astenda_kahend_rek1(a, n // 2) * astenda_kahend_rek1(a, n // 2)
    return astenda_kahend_rek1(a, n // 2) * astenda_kahend_rek1(a, n // 2) * a

// <![CDATA[

document.write(astenda_lihtne_iter());

// ]]>

def astenda_lihtne_iter(a, n):
    tulemus = 1
    for i in range(n):
        tulemus = tulemus * a
    return tulemus

// <![CDATA[

document.write(astenda_kahend_rek2());

// ]]>

def astenda_kahend_rek2(a, n):
    if n == 0:
        return 1
    pool_aste = astenda_kahend_rek2(a, n // 2)
    if n % 2 == 0:
        return pool_aste * pool_aste
    return pool_aste * pool_aste * a

View this question

Crowdly

Algoritmid ja andmestruktuurid (LTAT.03.005)

Want instant access to all verified answers on moodle.ut.ee?