Chodzi o ten algorytm (http://sun.aei.polsl.pl/~sdeor/students/aa/minmax3.pdf)
Ile dokładnie będzie wynosiła złożoność pesymistyczna?
Zapomniałeś gdzieś podłogi czy sufitu.
http://slimak.onet.pl/_m/matury/pytania/mat_2002/informatyka/a1.pdf
http://slimak.onet.pl/_m/matury/pytania/mat_2002/informatyka/a1_sch.pdf
Tu masz rozwiązanie :)
dalej nie wiem o co chodzi, z tą podłogą i sufitem też nie rozumiem.
Trzymam się tego że złożoność pesymistyczna to złożoność w najgorszym przypadku, a najgorszy jest ten 2 przypadek.
- T(pes) w przypadku nieparzystej liczby n wynosi 1 operacja przed iteracją plus 3(k-1) operacji w interacji i 2 po interacji = 3/2n-3/2
O ile dobrze pamiętam, podłoga to zaokrąglenie w kierunku zera, a sufit to zaokrąglenie w przeciwnym kierunku. Skoro znalazło się to w rozwiązaniach matur to oznacza, że powinno być to w materiale dla liceum. Więc w czym problem? Wzór podany w drugim PDFie pasuje do obu przypadków (tzn nieparzystej jak i parzystej liczby elementów).
niemożliwe że pasuje dla parzystej i nieparzystej liczby elementów, w moim podręczniku jest napisane tak:
http://img171.imageshack.us/img171/9350/ksiazka.png
i nagle ostatecznie został wybrany drugi przypadek, dlaczego nie pierwszy?
K*************RWAAAAAAAAAA! Tam jest sufit. Jak nie widzisz to załóż okulary.
http://pl.wikipedia.org/wiki/Pod%C5%82oga_i_sufit
Dla n nieparzystego:
3n/2 - 3/2 = sufit(3n/2) - 1/2 - 3/2 = sufit(3n/2) - 2
Dla n parzystego:
3n/2 - 2 = sufit(3n/2) - 2
a ja na początku myślałem że to nawias kwadratowy...
