Content deleted Content added
Citation bot (talk | contribs) Alter: journal. Add: authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | via #UCB_webform 155/1912 |
m Open access bot: doi added to citation with #oabot. |
||
Line 45:
===Median===
This particular case is of special interest since finding the [[median]] has several applications.<ref name=heriel>{{cite journal|first1=Sariel|last1=Har-Peled|author1-link=Sariel Har-Peled|first2=S.|last2=Muthukrishnan|title=Range Medians|journal=ESA|year=2008|pages=503–514}}</ref> On the other hand, the median problem, a special case of the [[selection problem]], is solvable in ''O''(''n''), using the [[median of medians]] algorithm.<ref name=tarjanmedian>{{Cite journal | last1 = Blum | first1 = M. | authorlink1 = Manuel Blum| last2 = Floyd | first2 = R. W. | authorlink2 = Robert Floyd| last3 = Pratt | first3 = V. R. | authorlink3 = Vaughan Pratt| last4 = Rivest | first4 = R. L. | authorlink4 = Ron Rivest| last5 = Tarjan | first5 = R. E. | authorlink5 = Robert Tarjan | title = Time bounds for selection | doi = 10.1016/S0022-0000(73)80033-9 | journal = Journal of Computer and System Sciences | volume = 7 | issue = 4 | pages = 448–461 | date =August 1973 | url = http://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf| doi-access = free }}</ref> However its generalization through range median queries is recent.<ref name=ethpaper /> A range median query <math>\operatorname{median}(A,i,j)</math> where ''A,i'' and ''j'' have the usual meanings returns the median element of <math>A[i,j]</math>. Equivalently, <math>\operatorname{median}(A,i,j)</math> should return the element of <math>A[i,j]</math> of rank <math>\frac{j-i}{2}</math>. Range median queries cannot be solved by following any of the previous methods discussed above including Yao's approach for semigroup operators.<ref name="morin kranakis" />
There have been studied two variants of this problem, the [[offline algorithm|offline]] version, where all the ''k'' queries of interest are given in a batch, and a version where all the preprocessing is done up front. The offline version can be solved with <math>O(n\log k + k \log n)</math> time and <math>O(n\log k)</math> space.
| |||