渐近符号和不同情况

Question

我想问：

1. 渐近符号与算法的最佳、最差和平均情况之间是否有任何关系？
2. 如果是，那么有什么关系？
3. 如果不是，那么使用渐近符号有什么用。

我从一开始就感到困惑。

Answer 1

“渐近符号”，顾名思义，就是符号。

您可以使用此符号来表达很多东西，包括：

• 比较两个数学函数的增长；
• 将算法执行时间的界限表示为输入长度的函数，包括最坏情况的执行时间和平均情况的执行时间。

“最佳情况”几乎从未被研究过，因为它过于乐观。