与えられた条件を満たすアルゴリズムはありますか？

-2

その最良の場合、時間の複雑アルゴリズムは平均的なケースの時間計算量と平均ケースの時間計算量は最悪のケースの時間計算量よりも小さいより少ないです。

ランダムアクセスマシン上のソートされていない配列内の要素をルックアップします。今あなたが_asymptotic_時間の複雑さを意味するなら、その答えは正しくなく、問題ははるかに面白いです。しかし、私はあなたの楽しみを台無しにするつもりはありません。 – Gene

ほとんど何ですか？先生があなたにこれを尋ねたら、彼はおそらくあなたが彼のクラスで議論されたアルゴリズムの1つを挙げることを望んでいます。 – m69

ヒント： "less than"の太字を特に入れる理由は何ですか？それは漸近的に漸減する必要があるということを意味しますか？例えばO（n）

ベスト≤平均≤ワーストは、定義によって常に真であるとすると、奇妙な質問です。

Quicksortには、O（n）/ O（n Log n）/ O（n²）の動作があります。【等確率順列の平均ケース。】

それはアルゴリズムから独立しているデータの統計的分布に依存するので、平均場合が存在しないことに注意する価値があります。したがって、平均的なケースの振る舞いは、最良のケースから最悪のケースに及ぶ可能性があります。

2017-10-25 07:52:41

クイックソートと言うことができます。典型的な良い実装は、最良ケースO（n）、平均ケースO（n log n）および最悪ケースO（n^2）を有する。 – Gene

@ジェネ：あなたは大丈夫です。私はあまりにも早く答えた。修正する。 –

ありがとうございます！私はO（n）時間を与えるクイックソートの実装を試みたことはありません... O（n） –

答えて