EFA - vypocet slozitosti rekurzivni funkce

Question

0

EFA - vypocet slozitosti rekurzivni funkce

BI-EFA

asked 2014-12-09 01:12:06 +0100

United121
1 ●2 ●2 ●3

updated 2014-12-09 13:08:43 +0100

Ahoj na fit wiki jsem nasel tento priklad a nejak nevim jak na to prijit ( presneji si myslim ze na fit-wiki to je blbe ) nejaky rady ? Určete časovou složitost následující rekurzivní funkce

aaa(x){
  if(x>0){
    int j = 0;
    while(j<x) j*=2;
    aaa(x/2);
  }
}

asi tam ma byt j=1 jinak to nema reseni efa_test_2013-12-10-chludil-d (nemuzu dat odkaz ... )

Rekurzivni prepis: aaa(x) = aaa(x/2) + log2(x)

me to vychazi na sumu k=0 do log2(x) pro log2(x/x^k) coz +- vede na slozitost stejnou jako v tom na fit wiki tj (log2(n))^2 ale jde mi spis o ten postuk ktery si myslim ze na fit je spatne

edit retag flag offensive close delete

Answer 1

0

answered 2014-12-09 09:42:09 +0100

Ondřej Máca
192 ●7 ●11 ●20

updated 2014-12-09 10:13:33 +0100

tak aspoň ten kod trochu zformatuj. Napiš ho normálně jako když programuješ, pak ho označ a klikni na preformatted text (5. zleva)

Já sem ten odkaz teda dám https://www.fit-wiki.cz/%C5%A1kola/p%C5%99edm%C4%9Bty/bi-efa/efa_test_2013-12-10-chludil-d akorát z neznámého důvodu nefunguje když se na něj klikne přímo, ale musí se zkopírovat

To zadání je tam stejně nějaký dívný. V tom whilu je jen inkrementace, takže ten while je tam úplně k ničemu. A kdyby to volání aaa bylo také v tom whilu, tam by tam byla naopak zbytečný podmínka if(x>0) protože by to vždycky ukončil ten while. Za předpokladu, že by teda to j začínalo od 1. Kdyby začínalo od nuly tak by se mohlo zdát, že ten if na začátku dává smysl, ale ve skutečnosti by se to zacyklilo. Takže to je pravděpodobně chyba zadání.

edit flag offensive delete publish link

EFA - vypocet slozitosti rekurzivni funkce

1 Answer

Your answer

Question tools

Stats

Related questions