[Algorytmy] IV OIG- pociąg- złożoność

cyberciq · Post autor: **cyberciq** » 6 kwie 2012, o 17:24

Czy ktoś kto robił zadanie pociąg z II etapu IV OIG pamięta może jaka była złożoność obliczeniowa na której rozwiązanie przechodziło wszystkie testy?

pozdrawiam

Mruczek · Post autor: **Mruczek** » 6 kwie 2012, o 20:44

\(\displaystyle{ O (n)}\) - wzorcowe, ale na \(\displaystyle{ O(nlogn)}\) też przechodziło.

gryxon · Post autor: **gryxon** » 7 kwie 2012, o 15:47

Wow \(\displaystyle{ O(nlogn)}\) do tego? Jak to wygląda?

Mruczek · Post autor: **Mruczek** » 8 kwie 2012, o 14:07

Posortować quicksortem, i potem wyszukiwanie binarne

cyberciq · Post autor: **cyberciq** » 13 cze 2012, o 16:02

Mruczek pisze:\(\displaystyle{ O (n)}\) - wzorcowe, ale na \(\displaystyle{ O(nlogn)}\) też przechodziło.

no ale nie na maks punktow