Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #32446

Złożóność obliczeniowa: udowadnianie rekurencji

Show all headers | View raw

Witam
Mam proste zadanie (ze słynnej książki: "Wprowadzenie do algorytmów" ze 
strony 87. nr 4.3-2) o treści:

Pokaż, że rozwiązanie równania T(n) = T(sufit(n/2)) + 1 jest O(lg(n)).

Postępowałem wg metody podstawiania podanej 4 strony wcześniej:
Przyjąłem tezę (do udowodnienia), że ma być T(n) <= clg(n) dla c>0
które zachodzi dla wszytkich m < n, a w szczególności dla m=sufit(n/2).
Tzn.:
T(sufit(n/2)) <= clg(sufit(n/2))

Teraz podstawiam to do równiania rekurencyjnego i mam:
T(n) <= clg(sufit(n/2)) + 1
= clg(n/2 + n mod 2) + 1

Tego już chyba nie trzeba redukować jednak należy sprawdzić, czy jest to 
<= clg(n)

Biorę n = 17 i mam:
clg(n/2 + n mod 2) + 1 = clg(8 + 1) + 1 = 4,1699
clg(n) = clg(17) = 4,0875

Czy to znaczy, że obaliłem tezę zdania? I że ten algorytm wcale nie jest 
O(lg(n))?!?

dzięki i pozdro
Szyk Cech

ps.: lg to logarytm o podstawie 2

Back to pl.comp.programming | Previous | Next | Find similar | Unroll thread

Thread

Złożóność obliczeniowa: udowadnianie rekurencji Szyk Cech <szykcech@spoko.pl> - 2019-03-06 20:22 +0100

csiph-web