algorithm - 予想実行時間と最悪の場合の実行時間

Question

私はランダム化されたクイックソートアルゴリズムを研究しています。このアルゴリズムの実行時間は、常に「予想実行時間」として表されることに気づきました。

「予想実行時間」を指定または使用する理由は何ですか？最悪の場合または平均的な場合を計算しないのはなぜですか？

Answer 1

予想される実行時間は、ランダムに選択された入力の平均実行時間を意味する場合があります。しかし、それがランダム化されたアルゴリズムである場合、多くの場合、入力ごとに、アルゴリズムによって行われたランダムな選択に関して予想される実行時間が意味されます。それがここでの意味です。n個のアイテムを入力するたびに、ランダム化されたクイックソートは平均して時間O（n（log n））で実行され、コイントス全体でのみ平均化されます。

この限られた意味で、予想される実行時間は、ランダム化されたアルゴリズムの実行時間の非常に防御可能な尺度です。アルゴリズムが内部でコインを投げるときに起こりうる最悪の事態だけを心配しているのなら、なぜコインを投げるのが面倒なのですか？あなたはそれらをすべて頭にするほうがよいでしょう。（ランダム化されたクイックソートの場合、通常のクイックソートになります。）

平均的なケースと最悪のケースは、コイントスの平均ではなく、入力の平均である場合、はるかに深刻な問題です。この場合、平均実行時間はせいぜい入力のタイプの変化に適応できない数値です---アルゴリズムの使用法が異なれば、入力の分布も異なる可能性があります。せいぜい、入力の仮想的な分布が実際の使用法であるとは知らないかもしれないので、私は言います。

コイントスに関して最悪のケースを見るのは、コイントスが不運でないときに速く走りたい場合と、コイントスが不運な場合でも遅すぎないようにしたい場合にのみ意味があります。たとえば、酸素供給用のレギュレーター（医療患者またはスキューバダイバー用）のソートアルゴリズムが必要であると想像してください。次に、ランダム化されたクイックソートは、ユーザーの便宜のために、通常は結果を非常に高速にしたい場合と、最悪の場合でもユーザーを窒息させない場合にのみ意味があります。これは、ソートアルゴリズムの不自然なシナリオです。これは、平均してクイックソートよりもそれほど遅くない非ランダムソートアルゴリズム（マージソートなど）があるためです。素数性テストのように、ランダム化されたアルゴリズムが多い問題についてはあまり考案されていません。ランダム化されていないアルゴリズムよりも高速です。次に、ランダム化されたアルゴリズムを使用して実行すると同時に、バックアップとして非ランダム化されたアルゴリズムを実行することをお勧めします。

（さて、なぜ酸素調節剤が特定の数が素数であるかを知りたいのか疑問に思うかもしれません。多分それは医療用コンピュータネットワークと通信する必要があり、医療プライバシーの理由で通信は安全である必要があります...）

Answer 2

「予想実行時間」とは、平均的な場合の実行時間のことです。漸近的に上限または下限（あるいはその両方）について話している可能性があります。同様に、最良または最悪の場合の実行時間の漸近的な上限と下限について話すことができます。言い換えれば、境界はケースに直交しています。

ランダム化されたクイックソートの場合、アルゴリズムが最悪の場合のO（n ^ 2）アルゴリズムよりも優れているように見えるため、予想される実行時間（O（n log n））について人々が話します（これは、漸近的ではありませんが、最悪の場合）。言い換えれば、ランダム化されたクイックソートは、ほとんどすべての入力について、たとえばバブルソートよりも漸近的にはるかに高速であり、人々はその事実を明確にする方法を望んでいます。そのため、人々は、最悪の場合のバブルソートのように漸近的に悪いという事実よりも、ランダム化されたクイックソートの平均的な実行時間を強調します。

コメントとGregの優れた回答で指摘されているように、固定された任意の入力でのアルゴリズムの実行中に行われたランダムな選択のシーケンスのセットに関して、予想される実行時間について話すことも一般的です。入力はアクティブなアルゴリズムによって受動的に作用されると考えるので、これはより自然なことかもしれません。実際、ランダム入力の平均と、その実行で構造の違いを考慮しないアルゴリズムについて話すのと同じです。これらの定式化は両方とも、入力とランダムな選択のペアのセット全体の真の平均よりも視覚化が容易ですが、どちらの方法でアプローチしても同じ答えが得られます。

Answer 3

アルゴリズムの動作が入力だけでなく、乱数ジェネレーターによって生成された値によっても決定される場合、アルゴリズムはランダム化されます。そのため、何が期待されているかを分析します。

最悪の場合の分析は入力のみです。

Answer 4

少し遅れて、長いコメントですが、追加することが重要だと思います。予想時間Tのアルゴリズムは、最悪の場合のO（T）アルゴリズムになる可能性があります。マルコフの不等式は、予想時間がTの場合、少なくとも1/2の確率で、アルゴリズムにかかる操作は2T未満になるため、次のようになります。アルゴリズムを実行し、2Tを超える操作が必要な場合は、これを停止して再実行します。これを最大log（1 / delta）回実行すると、最大でdeltaの失敗の確率が得られます。したがって、失敗の確率がデルタである時間計算量O（T * log（1 / delta））が得られます。しかし、ログが非常に小さいため、これはすべての実用的な理由から、失敗の確率が0のO（T）アルゴリズムです。