4-12-l Nakanarusawa
Hitachi 316
」APAN
ヽ︱ノ／
lbaraki University
２
Faculty of Engineering
ｑ
Department of lnformation Science
﹄”
by Tatsuya MO丁 OKI
多 →
η ′
Ｐゝ
A Note on Upper Bounds for Selection Problem
Keywords :
Minimum comparison selection,
worst― case analysis,
optimum sorting,
computational complexity
-2-
1. Introduction
According to Knuth[6], the hiStOry of selection problem 9oes back to
RevoC.L.DodgsOn[2]who pOinted out in 1883 that the second best player
often loses the second prize in lawn― tennis tournaments; about 1930 Hugo
Steinhaus posed the problem of finding the minimum number of tennis matches
required to select the first― and second‐ best players from π contestants,
assuming a transitive ranking: and now the Steinhaus problem is generalized
to our selection problem of finding the worst― case minimum number of
comparisons y。
numbers.
(η
)required to select the t― th largest from れ distinct
By symmetry, we have
L(η )=L`づ +1(4)・
Thus we may assume that lく
hroughout this paper lo92 iS denoted
づ
≦
:l`1. 丁
by 19・
Many people have made efforts to give good upper/1ower bOunds fOr
the problem.
As for lower bounds, Kirkpatrick[5] unified the theory:
he showed that
回
ｌ
ｄ
ｅ
︲ ｉ
ａ
ｔ
ｅ
ｄ
ｆ
ｓ
Ａ
ｕ
ｓ
︲
ａ
ｅ
ｃ
ｒ
﹃
叫
ｉ
ｓ
ｒ
ｓ
ｅ
ｔ
ａ
ｈ
ｔ
ｌ
２ ０ ｄ ｃ
一 ｎ
ｔ
ａ
ｈ ｔ
ｄ ｎ
ａ
ｕ ｐ
ｒ ｏ
協ヽ
ｕ
ｅ
∝ ｒ
Ｌ多 ｈ
ｔ 。
ａ
Iず
lts.
0
See Kirkpatrick[5]for a
paper Hadian and Sobel[3] showed
that
+(じ -1)Rg(4_じ +21.
)y― じ
りη
(2)
Several refinements(e,go Hyafil[4], Vap[8])were dOne by constructing
variants of the Hadian― Sobel algorithm, but these are all essentially
small improvements on (2); the Hadian― Sobel algorithm and its variants
3-
ne9d
θ(4194)cOmparisOns
when t嗜 . Until 1972 it was not known Whether
the selection problem inherently needs
Blum et al.[1]obtained the
Schё nhage
Schё nhage
val ues
θ(η )upper
bOund3 and further study, due to
づ,1, i.e・
et al.[7], led tO a much sharper upper bound for
ア
レ/21(4)<34+ο
Since
θ(419η )comparisOns; finall y,
=「
(η )。
et al.'s scheme can be easily generalized for general
of ι, we obtaln
(4) for everyう 。
L(4)」 が°
(3)
Let us now consider a question: For what values of
わ
asymptotically surpassed ?
r ttdrぷ
u鴛
where p=0.203688 。
for づくpη o
ι
(3)can be
Blum et al.[1]cOnsidered the similar question
學型IIttI「 √茅
for O<q」
Thus their (♀
:lη
+ο (4))― al gOri thm
HOw about the case of Schδ nhage et al.'s ?
(4)
can be surpassed
After a rough
comparison of (2)and (3), the Hadian― Sobel algorithm is seen to give
a better upper bound than Schё nhage et al.'s only for
very small values
e Ы
tt
¨ に おrづ 七 .ht∞ 面deri明 訥
's result, this
d d.
ought to be considerably improved.
In this note, we generalize (4)by applying the Blum et al.'s scheme
to a general (θ η+ο (4))― algorithm, and show that the qeneralized result
can be surpassed when we apply the scheme to the generalized Schё
et al。 's (34+ο (4))― a190ri
thmo
nhage
ln addition, we show that there exists
an asymptotically optimal selection algorithm provided that
Explicitly speaking, our results are:
4-
づ=ο (4).
ｆ ｆ ｆ
」
(iil)Ifじ =ο (4),ち (4)=が ο
(η )。
ｆ ｆ ｆ
却
ｇ
(il)
m su
λ
ｒＬＨ
９
ｎ
﹂洲
Ｏ
ｔ 十
Ｃ
ｅ
︲
ｅ却
ｓ
ｇ
ｒ Ｈ
ｒ ｌ．
ｏ
ｆ ２
ｈ ｌ
ｔ 一
ｍ ︺″
+1(4)
０ ＋
))
︲
．
ｒ ↑
(θ η+ο (η
ｇ
θ
ｌ
ｌ
′
︲′
︲
︲
↓︲︲
ａ
く
・
(1)If there exlsts a
9=0
0く 9<itiL
農
9=0
0<9<:
塞
2. A19orithm
In this section, we introduce an algorithm, due to Blum et al.[]],
which asymptotically surpasses Schё nhage et al.'s for づく ・ 丁he contestants
:η
really constitute a tOta1 0rdered seti but the order is initially not known,
and at any stage the algorithm's knowledge of inequality relations between
contestants is given by a partial order or equivalently a Hasse diagram;
for example
e。
lndicates that b<a, dく a and dく c.
The following is an algorithm obtained from B]um et al。 's by
interchanging step l and step 2.
A19orithm SELEC丁
[A,ρ ]
(丁 his
algorithm selects the
ι―th
largeSt from
η distinct
elements.
be chOsen
lateri p is any positive constant and A is any algorithm
丁his
contains two parameters p and A which will
solving the selection problem。
)
1. If じ>Pη , then select the t― th largest by using a19orithm A.
-5-
舞
︰ｌ
Ｌ
ｓ Ａ了 ︱ １ ０
ｔ
ｅ ｐ ＯＩＩ１０
Ｃ
ｅ
ｒ
ａ
︻
Ｐ
ｍ
Ｏ
Ｃ
ｎ ｏ ●
ｅ
ｍ ｒ ｏ
ｅ ・
ｌ ｏ
ａ
︲
η ｈ
ｎ
ａ ｏＴｌｌｉ■ｏ
ｏ ｅ
ｔ
ｌ
．
ｔ
ｒ
ａ
Ｐ
２
lnto
pairs and possibly one
leftover, and
(0)
︱︰ Ｌ
知
3. Select the じ―th largest m from
larger elements of step 2 by using
(recursively)SELEC丁 [A,p].
discard
4. Discard all elements known to be larger than m, since these cannot
be the t― th largest.
5。
Select the t― th largest from the remaining elements by using algorithm
A.
3. Analysis
(4))― al gOri thm.
ズ9)=脚
７
+ο
(ο η
ｅ Ｓ
Ｗ Ａ
In this section,
investigate how SELECT[A,p]can Surpass a general
a matter of convenlence, we lntroduce a notation
(η
Su
″
巧 ―
)
,3,」・
(5)
丁heorem l
If there exists a (θ η+ο (4))― algorithm fOr select10n, call ed
PICK(θ ), then SELEC丁 [PICK(θ ),ft「 ￨]bringS
abOut a upper bOund
if 9=o
砦 ng却
if O<9<が
if iが
Pr00fo
,3
Let p be any positive number, and let o(じ ,4,P)be the wOrst―
case number of cOmparisons required in SELECT[PICK(θ ),p].
O(じ ,η
,P)="+ο (4)
for
Obviously
じ>ρ η。
(6)
For づ<pれ , since SELECT[PICK(θ ),P]is called
l釧
t=「
times and for each 」―th ca1ling, 1く Jく 多, the number of cOntestants is
r/2」
′
L,
頑
ち
ち
J二
ぜ
夏些
/2も
+θ
step 2
= η―η/2t
/2ち
も
14/2tl■ tlべ
“step l
初■
al→
)
step 5
+ο 4/2t
+2θ tづ +ο (4)
= η+(θ -1)η /2t+2θ tづ +ο (κ )。
(7)
By combining (6)and (7), we obtain
aれ p可
:〔
卜
ｅ
〓
Ｐ
¨ 洲一
物
Setting
０
from (5),
θ
ｖ
＜ ｆ１︲︲ノ
劉︲︲ ．
．
９
丁hus
a liZ Q
島鋼 タバ
111″ 2L釧 受ο
and the factり η)」 (づ ,η ,P)
-1)/2「
θ
lg号 1+2θ
9 1gテ
￨: :]￨<P
if Oく 9>P
the theorem.
Q.E:D.
-7-
It should be noted that setting p=f:l minimizes the right hand side
Of (9); thus we cannot obtain a better upper bound from (9).
丁o
see
this, let F(P,9)be the right hand side of (9), and remember that p is
an arbitrary positive number in (9)。
ob宙 ously
For 9=0, the proposition is
true.For 9>0,since nヴ vattes over{1,2,3… }面 th
varying over{′
19、 P},and
since Oく ゥ
Pヽ
implies P(P,9)=θ =1+(σ -1)/20+2θ 9oO,
we obtaln
mi np>OF(P,9)=min{1+(ο -1)/2た +2θ た引 た=0,1,2,...}.
Now by an elementary analysis,
-1)/2た +2θ た
面n{1+(θ …
1)/2た +2ο た
91た =6,1,2,...〕 =1+(θ
9
if and only if
(1)た =O
andが
,
+2)多
Hence
９
１ １ ９
降撃
一
一
一
一
〓
′
Ｆ
０
＞
ｐ
ｍ
ｎ
ｆ ／ ｆ ／
降
or(ii)た >l and(θ -1)/(θ
`2た
くθ_1)/(θ・2た
+1)。
がタ
2た +2θ た
9
・2た
り and(θ -1)バ θ
lgf::1 +2ο
2「
+2)≦
9119f:11
9<(ο
-1)/(θ・2た
+1)
::h::wi:〔
As a corollary of the proof of ttheorem l, we have:
Corollary 2
Proof.
val ues
=ο (4),■ (4)〓 がο
1f ι
(4)。
°
Let P be any positive constant.
ofれ , we
+
l+■
η
I尊 }軍
丁hen
for sufficient large
雰ly(r),T孝 ￨メ 軌算学
8
丁hus
■(4)=1.
lim
4-
Q.E.D。
η
From (3)and ttheOrem l, we Obtain
if 9=0
if O<9く
き
if呂
Can this be surpassed ?
Let us nOw reconsider the proof Of ttheOrem l.
Suppose that p is any positive number, and that GS denotes the generalized
Sch6nhage et al.'s algorithm.
GS is roughly given in Fig.1.
The initial
step of GS is a pairing step; especially fOr GS invoked at step 5 of
SELEC丁
[GS,p], the initial pairing step is tO fOrm a Hasse diagram
′
１ １
′
１
︰
１
ｌ
ｌ
′
ヽ
′
、
一 ・
４ １ ．多 ・
ｐ
ｅ
卜 ｅ
・
ｅ
Ｓ
ｓ
ａ
constitute
Ｖ ｔ ︶ Ｈ ¨
ａ ｓ
Ｓ ａ
slnce after
９ １ １ ６
０
９ １ １ ６
０１１１０
０１１１０
But we can
comparlsons Out of these づ (Or づ-1)comparisOns,
of SELEC丁 [GS,P]the remaining 2づ (Or 2づ -1)elements
diagram
(0)
丁hus
(7)can be improved in SELEC丁 [GS,p]:
■ ―
at“ ,Pと
IJ=fL4/it+澄
十
ο
/2ち
(η /2ι
)+t(3(2づ )―
(づ
J)+θ (じ ))
step 2
=
丁his
η+21 tn+5ι ι+ο (4)
leads to the following theorem in the same manner that (7) leads
Theorem l.
丁heorem
3
if 9=0
if O<9<:
if墓 4
In conclusion, the bounds for 7(9), due tO ttheorem 3 and (1), are
illustrated in Fig。 2.
Note that for (2た +1)づ ―(2た +1)<η <(2た
号
Fg型 1:ユ 1=￨￨+1
:: li:i:IIlillll;:ll:〔
ｆ
ｔ
た ＞
２ １
′ヽ ＋
一 １
．多 ＋
た
＞
１ ２
＋ ′ヽ
１ ＜
＋ η
た ＜
２ ＞
ｌ
2た +1)
１
ｆ
2た +1)
／
１ ＜
１ ［
一
。多 ｏ多 ｏ多
一
η ︱
１ ．
１
百け ．
＋
︱
＜
¨
¨
・・
‘
Of
し■+1+1)<9<1/(2た
1/(2た
+1+1),た
-1, た>0
+1),
同一
ｆ ｆ
９
た
一
２
ｙ 一
ｒ た
ａ ｒヽ
１ ＋
１ た
ｏ
ｒ
降
ｏ
ｃ
ａ ＞ 一
〇 ９
ｔ ＜
７
This leads
多 ．
多 ヽノ
．
ｌ
た た
ｒ
Σ
<ぅ _21lg嘲
Oく 」
2た +1)
-1, 0く た,
￨_2
小釧
ん
一
丁hus
+1+1)づ
Acknowl edgments
l wish to thank the referee for his kind and detailed comments,
and Profo J.Takeda for his careful reading.
二10-
>0
References
[1]M.Bl um, RoW.Floyd, V.Pratt, R.L.Rivest and R.E.丁 arjan, 丁ime 3ounds
for Selection, 」.Comput.Systems Sci. 7(1973)448-461.
[2]C.LoDodgson, StoJames's Gazette, August l(1883)5-6.
[3]A.Hadian and M.Sobel, Selecting the t― th Largest Using Binary Errorless
Comparisons, 丁echoRep.121, Dept. of Statist。
[4]L.Hyafil, Bounds for SelectionD SIAM
, Univ. of Minneapolis, 1969.
」.Comput.
5(1976)109-114.
[5]DoGoKi rkpatrick, A Unified Lower Bound for Selection and Set
Partitioning Problems,
」.ACM
28(1981)150-165。
[6] DoE.Knuth, ::The Art of Computer Programmingi', voll.3 Sorting and
Searching, Addison― Wesl ey, 1973.
[7]A.Schё nhage, M.Paterson and N.Pippenger, Finding the Median,
JoComput. Systems Sci。
13(1976)184-199.
[8] C.K.Yap, New Upper Bounds for SelectiOn, Commun.ACM 19(1976) 501-508.
-11-
IMI NAttABLE?
Fig.1.
-12-
い
ｅ
ｐ
＼ｐ
ｕ
い
r bound
(≒ ,等 )
け
,争
ゃ
ｅ
ｗ
＼ｏ
︲
(缶 ,2)(告
r bound
(き ,評 )
(与 ,り
Fig.2.
-13-
© Copyright 2024 ExpyDoc
