アルゴリズムイントロダクション Chapter 9

順序統計量とメディアン
配列中のk番目の大きさの値は最悪でもO(n)で取れますよという話。このChapterでPart IIは終わり。Part IIIはデータ構造。

9.1-2

A:最小値の候補だが、最大値ではないもの
B:最大値の候補だが、最小値ではないもの
C:最大値・最小値の候補でA,Bでないもの
とする。

最初は、A:0,B:0,C:n
最終的に、A:1,B:1,C:0にする
A,Aの比較は、Aの数を1減らす
B,Bの比較は、Bの数を1減らす
A,Bの比較は、「なにも変えない」か、「A,Bから1ずつそれぞれ減らす」かのどちらか
A,Cの比較は、Cが1減り、「Bが1増える」か「そのまま」かのどちらか
B,Cの比較は、Cが1減り、「Aが1増える」か「そのまま」かのどちらか
C,Cの比較は、Aが1増え、Bが1増える

ここで、Cはまだ一回も比較されていない物なので値は自由に選べる（ワーストケースなので）ので、Aの任意の要素がBの任意の要素より小さい状況を作れる。そこで以下の5,6,7ルールは
5.A,Bの比較は、なにも変えない
6.A,Cの比較は、Cが1減り、Bが1増える
7.B,Cの比較は、Cが1減り、Cが1増える
とできる。このルールの元では少なくとも $\lceil 3n/2\rceil - 2$ だけ比較が必要

9.3-7

Aのメディアンを取って、メディアンとの距離を配列の全要素について計算する。メディアンとの距離がk番目のものを見つけてごにょごにょする。

9.3-8

二分法。Xからpivot=X[i]をとって、Y[n-i]付近の要素を見てメディアンかどうか判定していく。

9.3-9

y座標のmedian / mediansの間を選ぶと極小になるからきっとそこが最短なんでしょう。

9-1

a

$i + n\lg n$

b

$n + i\lg n$

c

$n + i\lg i$

9-2

b

ソートして最初から重みを足しつつみていく

c

二分法。medianを見つけて、それでPartitionしつつそれぞれの分割のweightの合計もとる。

d

pで微分すれば示せる

e

座標ごとの重み付きメディアン