Mozk https://blog.hatena.ne.jp/Mozk/ 壊れた計算機 https://mozk-2.hatenadiary.org/ CLRS 順序統計量とメディアン 配列中の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増える」か「そのまま」… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmozk-2.hatenadiary.org%2Fentry%2F20100207%2F1265550666" title="アルゴリズムイントロダクション Chapter 9 - 壊れた計算機" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2010-02-07 22:51:06 rich https://mozk-2.hatenadiary.org/entry/20100207/1265550666 1.0 100%