Cześć wszystkim,
Czy mógłby mi ktoś wytłumaczyć, na czym polega i jak się rozwiązuje tego typu zadania?
Treścią zadania jest tytuł wątku
NUM(tab,a,b){
L=b-a+1;
if(L<5)
return 3;
else{
k=ceil(L/5);
return tab[a+2*k-1] + NUM(tab, a+2*k, a+3*k)
}
}
Nie pytajcie, ile wynosi b i a, bo tego nie mam podane ;)
Jedynie porównanie jakie tutaj widzę to porównanie w ifie. Funkcja jest rekurencyjna i wywołuje siebie tylko w jednym miejscu, wobec czego ilość porównań jest równa maksymalnemu zagłębieniu rekurencji.
Należy prześledzić jak zmienia się L w zależności od stopnia zagłębienia. Jak na dłoni widać, że L zmniejsza się około pięciokrotnie przy każdym rekurencyjnym zejściu. Skoro L z każdym krokiem zmniejsza się o stały współczynnik (większy od 1, ale to oczywiste, bo inaczej nie byłoby zmniejszania) to po mniej więcej logarytmicznej liczbie kroków dojdziemy do L mniejszego od zadanej stałej. Stąd złożoność funkcji jest logarytmiczna.
Dzięki, w teorii już zrozumiałem. Ale czy jest możliwość sprawdzenia ilości wykonanych powtórzeń, nie znając podawanych na początku argumentów a i b?
Rozpisz sobie. Dodaj sobie indeksy do zmiennych oznaczające poziom zagnieżdżenia (tutaj ich wartości są efektywnie stałe, więc można tak spokojnie zrobić).
Wtedy:
L1 = b1 - a1 + 1
k1 = ceil(L1 / 5)
a2 = a1 + 2 * k1
b2 = a1 + 3 * k1
L2 = b2 - a2 + 1 = a1 + 3 * k1 - (a1 + 2 * k1) + 1 = k1 + 1
k2 = ceil(L2 / 5)
...
L3 = k2 + 1
k3 = ceil(L3 / 5)
...
L4 = k3 + 1
k4 = ceil(L4 / 5) = ceil((k3 + 1) / 5) = ceil((ceil(L3 / 5) + 1) / 5) = ceil((ceil((k2 + 1) / 5) + 1) / 5) = ceil((ceil((ceil(L2 / 5) + 1) / 5) + 1) / 5) = ceil((ceil((ceil((k1 + 1) / 5) + 1) / 5) + 1) / 5) = ceil((ceil((ceil((ceil(L1 / 5) + 1) / 5) + 1) / 5) + 1) / 5) = ceil((ceil((ceil((ceil((b1 - a1 + 1) / 5) + 1) / 5) + 1) / 5) + 1) / 5)
Zależność jest widoczna gołym okiem i teraz spokojnie można podać wzór na n-tą wartość L bądź k. Rekurencja kończy się, gdy L < 5. Nie widzę specjalnie sensu wyznaczania dokładnych zakresów początkowych L dla których jest osiągany dany stopień rekurencji. Z wzoru łatwo dopatrzyć się ciągu geometrycznego o współczynniku < 1, a wyrazy takiego ciągu zbliżają się do dowolnej odległości od zera w logarytmicznej liczbie kroków.
Taka możliwość jednak jest. Możesz podejść do zadania analitycznie, albo po prostu odpalić funkcję dla różnych parametrów. Konkretne wartości dla a i b nie są ważne, ważna jest tylko różnica, więc możesz przyjąć, że a jest zawsze równe 0 i wtedy badać poziom zagnieżdżenia dla różnych b.