Równania rekurencyjne dla kodu

0

Powie mi ktoś jak obliczyć złozoność takiego kodu na podstawie równania rekurencyjnego (jak się pisze takie rownania)?
:


int location (int low, int high){
int mid;
if(low>high) return 0;
else{

mid=(low+high)/2;
if(x>s[mid])

return location(low,mid-1);
else return location(mid+1,high);
}

}
0

Rozumiem że to jest nieudolny kod dla szukania połówkowego? Zapisz je iteracyjnie, co trudne nie jest i złożoność będzie oczywista.

1

Jakie iteracje, jak napisał, że rekurencyjne równanie ma ułożyć. Ma już przecież rekurencyjną implementację. To prawda, nieudolna, bo nie ma warunku stopu. Jak już będziesz miał swój przedział z jedną liczbą, to powinieneś zwrócić jej indeks.

A z każdym kolejnym wywołaniem skracasz swój przedział o połowę.
Poprawna implementacja powinna mieć złożoność opisująca wzorami:
T(1) = 1
T(n) = T(n/2) + 1

Wyliczenie samej złożoności obliczeniowej pozostawiam jako ćwiczenie.

0

Żeby wyliczyć złożoność trzeba rozwiązać podane równanie rekurencyjne.
Tu masz przykład jak:
http://4programmers.net/Forum/C_i_C++/150919-optymalizacja_rekurencji?p=984625#id984625

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0