N個の独立して同一に分布した浮動小数点値のセットのトップk要素を見つけるタスクを考えてみましょう。プライオリティキュー/ヒープを使用することにより、我々は、すべてのN個の要素の上に一回反復し、次の操作によって設定されたトップ-Kを維持することができます。トップk要素を見つけるための平均時間複雑度
要素xは、ヒープの頭よりも「より悪い」の場合:廃棄のxヘッドを取り外し、X⇒複雑性O(ログK)
最悪の場合の時間複雑さの挿入:(1)
要素xがヒープの頭よりも "良好" であれば複雑さOを⇒このアプローチは明らかにO(N log k)ですが、平均時間の複雑さはどうですか? IID-仮定、時間をかけてO(1)操作が増加する確率のために、私たちはめったに(kはログ)高価なOを実行する必要がない、特にkについて< < N.
は、この平均時間ですいずれかの引用可能な参照に文書化された複雑さ?平均時間の複雑さは何ですか?あなたの答えの引用可能な参照がある場合はそれを含めてください。
IMO for k << Nでは、複雑さは漸近的にO(N)に近づく。 –
私は、 'citable reference'を求めることは、[help/on-topic]に従って、[so]のトピックではない、推奨の質問として分類することをかなり確信しています。質問を適切に変更してください。 – Dukeling
@Dukeling:私は推薦を求めていません。ユニークな回答があるように質問を修正する必要がありますか?例えば、この結果を含む_first_の出版物を尋ねることによって?私にとっては、そのような参照が全く存在するかどうかという疑問があります。 – bluenote10