Odp. na pytanie 3:    Szukamy minimum tej funkcji W(n) =  [(n-1)/k] + (k-1) ze względu na k.  Zbadajmy pochodną funkcji  f(k) =  (n-1)/k + ( k-1). Mamy  f’(k) = (-n+1)/k2 + 1. Zatem f’(k) = 0 dla k =  Ö(n-1). Funkcja f przyjmuje wartość minimalną dla k = Ö(n-1).  Koszt pesymistyczny algorytmu SKOKI(k)  jest najmniejszy dla k= éÖ(n-1)ù.

Zamknij okno