[Teoria złożoności] Złożoność rekurencyjna

krystian987
Użytkownik
Użytkownik
Posty: 24
Rejestracja: 21 lis 2016, o 16:51
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 2 razy

[Teoria złożoności] Złożoność rekurencyjna

Post autor: krystian987 »

Witam mam problem ze złożonością rekurencyjną. Mam ją wyznaczyć metodą podstawiania.
1 .Czy jeśli mam np.
\(\displaystyle{ T \left( 1 \right) = 0}\)
\(\displaystyle{ T \left( n \right) = T \left( \frac{n}{2} \right) + 1}\) dla parzystego \(\displaystyle{ n > 1}\)
\(\displaystyle{ T \left( n \right) = T \left( \frac{n + 1}{2} \right) + 1}\) dla nieparzystego \(\displaystyle{ n > 1}\)
to muszę wyznaczyć złożoność najpierw dla parzystych a później dla nieparzystych czy wystarczy dla jednego przypadku

2. Jak obliczyć złożoność w takim przykładzie :
\(\displaystyle{ T \left( 1 \right) = 1}\)
\(\displaystyle{ T \left( n \right) = T \left( n – 1 \right) + n}\) dla \(\displaystyle{ n > 1}\)
Ostatnio zmieniony 6 sty 2017, o 21:29 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
Mariusz M
Użytkownik
Użytkownik
Posty: 6903
Rejestracja: 25 wrz 2007, o 01:03
Płeć: Mężczyzna
Lokalizacja: 53°02'N 18°35'E
Podziękował: 2 razy
Pomógł: 1246 razy

[Teoria złożoności] Złożoność rekurencyjna

Post autor: Mariusz M »

2. Wystarczy zsumować część niejednorodną , chociaż jak chcesz to możesz użyć funkcji tworzącej
ODPOWIEDZ