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?
0
0
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.
0
_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.
0
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.