Revision history [back]

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);="" }="" }<="" p="">

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

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);="" }="" }<="" p="">
j*=2;
    aaa(x/2);
  }
}