これは、Quicksort の分割アルゴリズムを使用して、n 個の要素の配列で k 番目に小さい数を見つけるアルゴリズムです。
small(a,i,j,k)
{
if(i==j) return(a[i]);
else
{
m=partition(a,i,j);
if(m==k) return(a[m]);
else
{
if(m>k) small(a,i,m-1,k);
else small(a,m+1,j,k);
}
}
}
ここで、i、j は配列の開始インデックスと終了インデックス (ji=n(配列内の要素の数)) であり、k は k 番目に小さい no です。上記のアルゴリズムの最良のケースと平均的なケースは何か、簡単に説明したいと思います。最良の場合、終了条件を計算するべきではないことを知っています。また、パーティションアルゴリズムには O(n) がかかります。漸近的な表記法ではなく、可能であれば正確な数学的結果が必要です。