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

Thread View: pl.comp.programming

1 messages

[T] Back to Threads [V] Tree View [G] Group Articles

1 total messages Started by Szyk Cech Wed, 06 Mar 2019 19:22

#215447

Author: Szyk Cech
Date: Wed, 06 Mar 2019 19:22

30 lines
1968 bytes

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

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads