1

私は最近、最初に重複のケースなしで、k 番目に最小の要素アルゴリズムを分析した後、プログラムを作成しました。

jただし、正確に重複がある場合に、配列の中央値などを見つけるために、予想される漸近的なランタイムを分析したいと思います。jそのようなコードを変更していないため、重複のためにパフォーマンスが少し低下します。

どうやって始めればいいのかわからない？誰かが私にそのような再発関係を指摘できますか?

n は入力配列のサイズです。

T(n) <= 1/2*T(3/4*n) + 1/2*T(n)

しかし、関連する重複キーをどのように処理するかは非常に不明です。

ありがとう

4

1 に答える 1

0

ここで示されているランダム化されたソリューションは次のとおりです。

 T(n) <= T(3/4*n) + n-1  =>  T(n) <= 4n

アルゴリズムの複雑さは依存する可能性がありますがj、線形時間よりも奇跡的に少ないとは思わないでください。なんで？サイズ n/2 のランダムな配列を取得し、それを完全に複製し、複製の問題に対して理想的なアルゴリズムを実行します。あなたが持っているでしょう

T(n) <= 4(n/2) => T(n) <= 2n

各要素が 2 回複製された場合 (正確にn/2複製)

于 2012-04-23T08:50:16.297 に答える