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}\)
[Teoria złożoności] Złożoność rekurencyjna
-
- 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
Ostatnio zmieniony 6 sty 2017, o 21:29 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.