トップk要素を見つけるための平均時間複雑度

Question

N個の独立して同一に分布した浮動小数点値のセットのトップk要素を見つけるタスクを考えてみましょう。プライオリティキュー/ヒープを使用することにより、我々は、すべてのN個の要素の上に一回反復し、次の操作によって設定されたトップ-Kを維持することができます。

• 要素xは、ヒープの頭よりも「より悪い」の場合：廃棄のxヘッドを取り外し、X⇒複雑性O（ログK）

最悪の場合の時間複雑さの挿入：（1）

要素xがヒープの頭よりも "良好" であれば複雑さOを⇒このアプローチは明らかにO（N log k）ですが、平均時間の複雑さはどうですか？ IID-仮定、時間をかけてO（1）操作が増加する確率のために、私たちはめったに（kはログ）高価なOを実行する必要がない、特にkについて< < N.

は、この平均時間ですいずれかの引用可能な参照に文書化された複雑さ？平均時間の複雑さは何ですか？あなたの答えの引用可能な参照がある場合はそれを含めてください。

Answer 1

i番目の最大要素と特定の置換を考えてみましょう。 k-sizedヒープに挿入されるのは、置換の（i - 1）より大きい要素のk-1より前に出現する場合です。

ヒープ挿入が起こる確率は、i < = kの場合は1、i> kの場合はk/iです。

これから、予想の線形性を使用して、ヒープ調整の数の期待値を計算することができます。 k/i = k *（1 + H（n））であり、これは、（i = 1〜k）1 + sum（i = k + 1〜n） - H（k））ここで、H（n）はn番目の高調波数です。

これは約k log（n）（k < < n）であり、そこからの平均費用を計算することができます。