Udowodnij czas działania algorytmu.

Odpowiedz Nowy wątek
2015-06-01 20:31

Rejestracja: 5 lat temu

Ostatnio: 5 lat temu

0

Witam wszystkich,

Mam mam problem z zadaniem z algorytmów. Studiuję informatykę, ale wyłącznie z powodu grafiki i nie ukrywam, że właśnie nawięcej problemu stwarzają mi właśnie algorytmy. Bez wysłania tego zadania do pani prowadzącej nie będe mogła przystąpić do egzaminu. Jeżeli ktoś byłby w stanie mi pomóc byłabym bardzo wdzięczna:

Udowodnij indukcyjnie, że 3n - 2n (trzy do n-tej minus dwa do n-tej) dla wszystkich n >= 0 reprezentuje czas działania algorytmu T(n):

T(n)
1 if n <= 1
2 then return n
3 else return 5T(n - 1) - 6T(n - 2)

Bardzo proszę o pomoc.

edytowany 8x, ostatnio: Karolina94, 2015-06-02 21:23

Pozostało 580 znaków

2015-06-01 20:56
Moderator

Rejestracja: 12 lat temu

Ostatnio: 1 miesiąc temu

0

Przyłóż się trochę do pisania postu.
3n - 2n


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell

Pozostało 580 znaków

2015-06-01 20:57
Moderator

Rejestracja: 16 lat temu

Ostatnio: 1 minuta temu

0

W Cormenie masz napisane jak liczyć złożoność rekurencji. A tu :

4programmers.net/Forum/Algory[...]iczeniowa_kodu_rekurencyjnego

Ktoś miał podobny problem


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2015-06-01 21:07

Rejestracja: 5 lat temu

Ostatnio: 5 lat temu

0

Wybaczcie za błędy. Kilka razy edytowałam post, ale dalej jakoś dziwnie się ten kod wyświetla.
Przeczytałam tamten post, ale nie rozjaśnił mi sposobu na indukcyjne udowodnienie tego algorytmu.

edytowany 2x, ostatnio: Karolina94, 2015-06-01 21:09

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0