eGospodarka.pl

eGospodarka.plGrupypl.comp.programming › Złożóność obliczeniowa: udowadnianie rekurencji
Ilość wypowiedzi w tym wątku: 1

  • 1. Data: 2019-03-06 20:22:14
    Temat: Złożóność obliczeniowa: udowadnianie rekurencji
    Od: Szyk Cech <s...@s...pl>

    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

strony : [ 1 ]



Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: