tag:blogger.com,1999:blog-3722233.post5355131035765998446..comments2024-04-17T04:33:37.511-05:00Comments on Computational Complexity: Finding the ith largest of n numbers for i,n SMALLLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-55695346987769305752008-10-21T14:32:00.000-05:002008-10-21T14:32:00.000-05:00Dorit Dor, Uri Zwick,Median selection requires (2+...Dorit Dor, Uri Zwick,<BR/>Median selection requires (2+eps)n comparisons. SIAM Journal on Discrete Mathematics 14, 312-325 (2001) (also see Zwick's homepage for draft)<BR/><BR/>refers to a 1974 TechReport by Kirkpatrick. As reported in Dor/Zwick, an exact formula for V(3,n), n>=50 is known due to Kirkpatrick. They also reproduce the exact formula. I haven't looked into Kirkpatrick's paper yet, might be difficult to obtain it.<BR/><BR/>If there is a uniform optimal algorithm in case i=3, what does it do for n<50? Please post about it if you find smth interesting.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16461248038626417202008-10-20T04:55:00.000-05:002008-10-20T04:55:00.000-05:00There is a paper "On the lower bound for minimum c...There is a paper "On the lower bound for minimum comparison selection", by Ruzicka, Wiedermann from 1978, cf. http://dml.cz/bitstream/handle/10338.dmlcz/103726/AplMat_23-1978-1_1.pdf showing the best known (in late seventies) lower bounds for the selection problem. I do not know whether these bounds have been improved since then.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21803660039252574942008-10-19T18:17:00.000-05:002008-10-19T18:17:00.000-05:00Andy, the canonical algorithm for i = 2 involves a...Andy, the canonical algorithm for i = 2 involves a tournament to find the maximum and then a tournament of the elements that lost to the maximum.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80161367817591450282008-10-19T14:13:00.000-05:002008-10-19T14:13:00.000-05:00Bill: as someone not familiar with the research of...Bill: as someone not familiar with the research of this problem, is there any reason to expect that this conjecture might be true? I see an algorithm for i=1 that begins with that, but is there a known, optimal algorithm of that form for i=2?<BR/><BR/>At this point the conjecture sounds a bit arbitrary, though no doubt helpful for the problem if we knew it to be true.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-169404799562951992008-10-18T18:49:00.000-05:002008-10-18T18:49:00.000-05:00Alejo, I don't think your analysis of quickselect ...Alejo, I don't think your analysis of quickselect is correct. In the best case, it takes ~ N compares (you get lucky and partition on i in the first pass). I believe the average number of compares (assuming the array is shuffled) is <BR/><BR/>~ 2 N + i ln ( N / i) + (N - i) ln (N / (N - i))<BR/><BR/>which is ~ (2 + 2 ln 2) N for i = N/2.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67075668049829335302008-10-18T15:20:00.000-05:002008-10-18T15:20:00.000-05:00Here a simple recursive algorithm that, in the bes...Here a simple recursive algorithm that, in the best case, requires about 2n comparisons to find the ith largest, independent of i. It relies on recursive partitioning. It assumes that partition() rearranges the list, placing a pivot element at location j, elements less than the pivot before j, and the bigger elements after j. Here is some pseudocode:<BR/><BR/>iThLargest(list, i) {<BR/> j = partition(list)<BR/> if (j is i)<BR/> return list[j]<BR/> else if (j < i)<BR/> iThLargest(list[1 to j-1], i)<BR/> else<BR/> iThLargest(list[j+1 to end], i-j)<BR/>}<BR/><BR/>The algorithm also uses about 2n comparisons in the average case. However, the worst case is quadratic in n.<BR/><BR/>There is also a well-known median-finding algorithm that runs with time linear in n, in the worst case. The median is the case i=floor(n/2).<BR/><BR/>AlejoAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86986818058153445992008-10-18T13:10:00.000-05:002008-10-18T13:10:00.000-05:00"In the same trend here is a paper about the minim..."In the same trend here is a paper about the minimal number of comparisons :<BR/>http://www.mat.unb.br/~ayala/4FordJohnson.ps"<BR/>Sorry i meant minimal number of comparisons for sorting.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29042963285650054542008-10-18T13:08:00.000-05:002008-10-18T13:08:00.000-05:00In the same trend here is a paper about the minima...In the same trend here is a paper about the minimal number of comparisons : <BR/>http://www.mat.unb.br/~ayala/4FordJohnson.ps<BR/>Usefulness of computing the exact minimal number of comparisons seems quite limited. <BR/>Daniel Lemire's algorithm seems to stress other motivations like working space and latency.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65844947694238059072008-10-18T03:42:00.000-05:002008-10-18T03:42:00.000-05:00Why on earth would anyone be doing computer search...Why on earth would anyone be doing computer searches for such algorithms?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91013290986337724242008-10-17T11:03:00.000-05:002008-10-17T11:03:00.000-05:00For a related problem, how many comparisons per el...For a related problem, how many comparisons per element does it take to find the max/min over windows of size c given an array of numbers? This is an important problem for people doing signal processing/computer vision. <BR/><BR/>If the windows have size c=n where n is the total number of elements, then this problem is just finding the max/min of a set and the number of comparisons needed is known (see any textbook). For the more general problem, the answer is *not* known, however see the following paper for a recent result:<BR/><BR/>http://arxiv.org/abs/cs.DS/0610046Daniel Lemirehttps://www.blogger.com/profile/01566622051558391310noreply@blogger.com