1
私は最近、k番目の最小要素アルゴリズムを解析した後、まず重複の場合を除いてプログラムを書いた。ドゥーピーによる選択ルーチン？
しかし、正確にjの重複がある場合、配列の中央値を見つけるための期待漸近実行時間を分析したいと思います。私はそのようなコードを変更していないので、パフォーマンスが遅くなるのは、j重複のためです。
開始方法がわかりません。誰かがこのような再発関係に向かって私を指摘できますか？
私は、nは、入力配列
T(n) <= 1/2*T(3/4*n) + 1/2*T(n)
の大きさですが、関与重複キーを続行する方法は非常に不明確だ次のことを、派生しました。アルゴリズムの複雑さはjに依存してもよいが、それは線形時間よりも奇跡的に小さくなるように期待していない
T(n) <= T(3/4*n) + n-1 => T(n) <= 4n
おかげ
重複しているときに我々はあなたが話している機能を持っていない限り、私たちはあなたを助けることができないがあるでしょう。 –