私は最近、最初に重複のケースなしで、k 番目に最小の要素アルゴリズムを分析した後、プログラムを作成しました。
jただし、正確に重複がある場合に、配列の中央値などを見つけるために、予想される漸近的なランタイムを分析したいと思います。jそのようなコードを変更していないため、重複のためにパフォーマンスが少し低下します。
どうやって始めればいいのかわからない？誰かが私にそのような再発関係を指摘できますか?
n は入力配列のサイズです。
T(n) <= 1/2*T(3/4*n) + 1/2*T(n)
しかし、関連する重複キーをどのように処理するかは非常に不明です。
ありがとう