Jako że biorę w tym roku (jak i rok temu i dwa lata temu) udział w konkursie informatycznym "Od algorytmu do programu", który polega na teście wiedzy oraz pisaniu programu w C (wczytanie jakichś danych z pliku i ich analiza) przy czym punktowana jest jak najmniejsza złożność. Chcąc jak najlepiej przygotować się do konkursu, jakie zagadnienia z algorytmiki powtórzyć? Algorytmy sortujące to na pewno, ale czy coś jeszcze? Czy znacie jakieś witryny WWW na których te rzeczy są przystępnie wyjaśnione? I jeszcze jedno pytanie: czy radzicie na konkursie stosować sztuczki takie jak mnożenie poprzez przesunięcie bitowe - program będzie szybszy, ale istnieje ryzyko, że osoba oceniająca kod tego nie zrozumie i da zero punktów.
0
1
to ci wystarczy spokojnie, nie wiem nawet czy lekko nie za wysoki poziom https://www-users.mat.umk.pl/~stencel/acm/algorytmika_praktyczna.pdf
osoba oceniajaca spokojnie zrozumie wszystkie sztuczki, ktore Ty uzyjesz m.in przesuniecia bitowe
0
A to nie jest tak że nowoczesne kompilatory same optymalizują /2 jako >>1 ? Skoro człowiek potrafi zoptymalizować to maszyna też tym bardziej. Optymalizacja polega raczej na kompromisie pomiędzy szybkością a rozmiarem programu. Jak rozwijanie pętli ?
0
A to nie jest tak że nowoczesne kompilatory same optymalizują /2 jako >>1 ?
Być może, ale tutaj będę oceniany za kod który napiszę, więc udowodnienie, że znam techniki optymalizacyjne będzie na plus.
1
Hmm, w jaki sposób może to być na plus, skoro sam wspomniałeś:
przy czym punktowana jest jak najmniejsza złożność.
Ja skupiłbym się na napisaniu dobrego, czytelnego algorytmu - nie warto bawić się w żadne >> 1 / << 1 czy 0x5F3759DF i nie wyobrażam sobie sytuacji, w której można by za coś takiego otrzymać ekstra punkty :-P
0
Kompiluj wszystko bez optymalizacji i sobie porównuj czasy, coś podobnego masz na polskim spoju + wyniki innych ludzi.
Możesz tam rozwiązać zadanie z Twoimi optymalizacjami i bez nich.
Jakbyś się decydował na spoja to wybieraj tylko zadania łatwe.