Nasza grupa dostała za zadnie na zaliczenie udowodnić metodą indukcji że:
\(\displaystyle{ T \left( n \right) = n\log n-n+1 = 0 \left( n\log n \right)}\)
oraz napisać złożoność
czy ktoś będzie w stanie pomóc z góry dziękuje.
[Teoria złożoności] Udowodnij metodą indukcji
[Teoria złożoności] Udowodnij metodą indukcji
Ostatnio zmieniony 26 cze 2013, o 14:45 przez Afish, łącznie zmieniany 1 raz.
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
-
- Użytkownik
- Posty: 5974
- Rejestracja: 28 lut 2010, o 19:45
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 15 razy
- Pomógł: 1251 razy
[Teoria złożoności] Udowodnij metodą indukcji
Masz wykazać, że \(\displaystyle{ n \log n -n +1 \in )(n \log n)}\)? Jeśli tak, to nie trzeba indukcji. Znajdź stałą \(\displaystyle{ C > 0}\) taką, aby \(\displaystyle{ n \log n - n + 1 \geq C \cdot n \log n}\).
[Teoria złożoności] Udowodnij metodą indukcji
To jest funkcja rekurencyjna i mamy udowodnić metodą indukcji że lewa strona = prawej