// Millised järgnevatest programmidest on keskmise ajalise keerukusega Θ(log n)? Eeldada, et jäägi leidmine ning arvude korrutamine, jagamine ja võrdlemine on keerukusega Θ(1). Märgi kõik sobivad vastused.

Question

// <![CDATA[
var ulObj = new Object();
ulObj.objektityyp = "programmidest";
ulObj.tyyp = "keskmise";
ulObj.keerukus = teeta() + "(log 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 Θ(log n)? Eeldada, et jäägi leidmine ning arvude korrutamine, jagamine ja võrdlemine on keerukusega Θ(1). 
 Märgi kõik sobivad vastused.

Answer

// <![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)

Answer

// <![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

Answer

// <![CDATA[
document.write(astenda_lihtne_iter());
// ]]> def astenda_lihtne_iter(a, n):
    tulemus = 1
    for i in range(n):
        tulemus = tulemus * a
    return tulemus

Answer

// <![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

Crowdly

// <![CDATA[ var ulObj = new Object(); ulObj.objektityyp = "programmidest"; ...

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