Mój problem wygląda następująco:
wczytuję ciąg n liczb, po czym chcę znajdować szybko minimum z danego przedziału, np. [1, 5].
Czy da się zrobić to szybciej niż w czasie liniowym względem długości przedziału? A jeśli tak, to w jaki sposób?
Mój problem wygląda następująco:
wczytuję ciąg n liczb, po czym chcę znajdować szybko minimum z danego przedziału, np. [1, 5].
Czy da się zrobić to szybciej niż w czasie liniowym względem długości przedziału? A jeśli tak, to w jaki sposób?
Jeżeli ciąg posortowany to pierwszy/ostatni w zależności od kierunku, jeżeli nie to szybciej niż O(n) nie da rady.
_13th_Dragon napisał(a):
jeżeli nie to szybciej niż O(n) nie da rady.
Jak to nie da rady!? A chociażby drzewa przedziałowe? Owszem, wymaga to wpierw stworzenia drzewa, ale potem na takie zapytanie odpowiadamy w czasie O(lg n). Sądząc po pytaniu autor chce wiele razy określać minimum dla przedziału, więc bardzo prawdopodobne, że O(n lg n + q lg n) będzie mu bardziej pasować.
Dla autora do poczytania i oglądania: http://was.zaa.mimuw.edu.pl/?q=node/8
A jeśli komuś bardzo zależy na rozwiązaniu liniowym O(n + q) to może się zabrać za MRQ, ale wtedy zapewne nie patrzyłby do tego wątku.
Wcale nie napisał ze chce to robić wiele razy. jeśli ma to robić raz to czas będzie liniowy. Jeśli wiele razy to nlogn.
Zarejestruj się i dołącz do największej społeczności programistów w Polsce.
Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.