algorithm - 对于任何算法，它的平均情况性能总是优于最坏情况性能，这是对还是错？

Question

我想这是真的，但我对这个答案不太自信。是否有一种算法在平均情况和最坏情况下具有相同的运行时间。我不确定答案是否正确。

Answer 1

在最佳、平均和最坏情况下，计算 1+1=2 是 O(1)。

一个稍微不那么简单的例子：确定长度为 n 的链表的长度在所有情况下都需要 n 步，所以在所有情况下都是 O(n) 。

Answer 2

错误的。例如：BinarySearch、ShellSort、HeapSort 等。