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);
}
}
Rozumiem że to jest nieudolny kod dla szukania połówkowego? Zapisz je iteracyjnie, co trudne nie jest i złożoność będzie oczywista.
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.
Ż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