渐近时间复杂度与最佳、平均和最坏情况输入的组合

Question

我被许多声称渐近符号与最好情况、一般情况和最坏情况的时间复杂度无关的说法搞糊涂了。如果是这种情况，那么下面的组合可能都是有效的:

1. 最佳情况 - 最佳情况输入的上限

为了尽可能好的输入，该算法执行的基本操作的数量永远不会超过n的某个常数倍。

对于平均输入，该算法执行的基本操作的数量永远不会超过n的某个常数倍。

对于最坏的可能输入，该算法执行的基本操作的数量永远不会超过n的某个常数倍。

为了获得最佳输入，此算法执行的基本操作数永远不会超过或小于 n 的某个常数倍数。

对于平均输入，该算法执行的基本运算的数量永远不会超过或小于n的某个常数倍。

对于最坏的可能输入，该算法执行的基本操作的数量永远不会超过或小于n的某个常数倍。

为了获得最佳输入，此算法执行的基本操作数永远不会小于 n 的常数倍数。

对于一个平均输入，由该算法执行的基本操作的数量绝不会少于n的某个常数倍数。

对于最坏的可能输入，该算法执行的基本操作的数量永远不会小于n的某个常数倍。

以上哪一项有意义？在实践中，根据输入增长执行所花费的时间来评估算法的效率时，通常使用哪些？据我所知，其中一些是多余的和/或矛盾的。

我真的不明白上限、紧边界和下限的概念与最佳、平均和最坏情况的输入无关。这是我越深入研究就越困惑的话题之一。如果有人能帮我澄清这件事，我将不胜感激。

Answer 1

所有陈述都是有道理的。

在实践中，除非另有说明，否则我们应该讨论所有情况下的最坏情况输入。

我们经常担心平均案例输入，尽管“平均案例”的定义有点狡猾。通常最好谈论“预期时间”，因为这是一个更精确的数学定义，对应于人们通常所说的“平均情况”。不幸的是，人们在这里经常草率，你经常会看到复杂性陈述，这些陈述指的是预期时间而不是最坏情况的时间，但没有提到它。

我们很少关心最佳案例输入。

不幸的是，也经常看到人们混淆最佳与最坏情况输入和上限与下限的概念，尤其是在so和其他非正式网站上。

你总是可以回到定义，就像你已经做的那样，来弄清楚陈述的真正含义。

“此算法在 X（n 2） 时间内运行”意味着给定函数 f（n） 表示在任何环境中的最坏情况下执行时间与问题大小的关系，该函数将在集合 X（n²） 中。

"此算法在X（n²）预期时间中运行"意味着给定函数f（n）在任何环境中对执行时间vs问题大小的数学预期，该函数将在集合X（n²）中。

最后，请注意，在任何环境中实际上仅适用于特定的计算模型。我们通常假设一个随机存取机，所以复杂性陈述对图灵机实现是无效的。