algorithm - どのアルゴリズムでも、その平均ケースのパフォーマンスが最悪ケースのパフォーマンスよりも漸近的に常に優れているというのは本当ですか?

Question

これが本当だと思いたいのですが、その答えに自信がありません。平均的なケースと最悪のケースの両方で実行時間が等しいアルゴリズムはありますか。そのときの答えが正しいかどうかはわかりません。

Answer 1

1+1=2 の計算は、最良、平均、最悪の場合で O(1) です。

少し些細な例: 長さ n のリンクされたリストの長さを決定するには、すべての場合で n ステップかかるため、すべての場合で O(n) です。

Answer 2

間違い。例: BinarySearch、ShellSort、HeapSort など。