クイックセレクトクラリティー化

Question

クイックセレクトの講義スライドでは、正確には「k」となりますか？

Answer 1

のは、あなたが数xを取ったとしましょう。

Lは、アレイ内のxより少ない数の集合と、集合の大きさは|L|

がEがアレイ内xに等しい数の集合とされ、セットのサイズは|E|

あります

Gは、アレイ内のxよりも大きな数字の集合とし、セットのサイズは|G|

だがソートされた配列、モミを想像してみましょうですst |L|番号(1 -> |L|)は、セットLに含まれています。

以下の|E|の数字(|L|+1 -> |L|+|E|)は、セットEに含まれています。

以下の|G|の数字(|L|+|E|+1 -> end)は、セットGに含まれています。

我々はkth最小の番号を探しているので、我々は3例があります。これは我々が探している番号がソートされた配列の最初の|L|数字であることを意味

1）k <= |L|を、私たちはを検索しますkthの数字はLです。

2）|L| < k <= |L|+|E|これは、ソートされた配列内で(|L|+1 -> |L|+|E|)の位置にあるので、Eの要素であることを意味します。 Eのすべての要素はxに等しいので、kthの最小番号はxに等しいことがわかります。

3）k > |L|+|E|これは、ソートされた配列内の(|L|+|E|+1 -> end)の位置にあるので、 'G'の要素であることを意味します。 kth最小の数よりも少ない|L|+|E|番号がすでに存在しているので、我々は、kから|L|+|E|を引くのは、それk'（k' = k - |L| - |E|）を呼び出してみましょう、とGにk'th最小の要素を検索することができます。