问为什么在邻接列表O中的操作是$的？

EN

我相信这个问题与另一个问题在堆栈溢出上的问题非常相似，请参考它，因为它可能已经回答了您的问题。为了完整起见，我也会尝试总结我对这个话题的理解，但我在这个问题上并不权威，所以如果我说错了什么，请随时纠正：

我能理解的是，当我们都知道最坏的情况是O(N)的时候，为什么图表上说操作是O(E/N)。嗯，这里有两个问题：

1. 假设大O意味着“最坏的情况输入”，但是，根据定义，我们不能假设这一点。
2. 图表上只写着O(E/N)，正如@domen评论的那样，文本应该更清晰，并指明它正在考虑的输入情况。

这里的一个快速回答是，大O可以用来“谈论”这两种情况。当我们谈论平均输入时，它将是O(E/N)，当我们谈论最坏的输入时，它将是O(N)。

现在，让我们看到一个更长的解决每个枚举问题的答案:相应地，对于“算法导论”一书，我们可以将大O定义为：

O(g(n)) ={ f(n)：存在正常数c和n0，使得所有n >= n0}都存在0 <= f(n) <= cg(n)

注意，这个定义没有提到最坏的情况，它只是说，如果我们有一个函数f(n)，并且我们可以提供一个常数c和一个n0，使0 <= f(n) <= cg(n)对于每n个>= n0，那么f(n)在O(g(n))中。因此，这里忽略了最坏的情况，如果我们可以提供一个函数f(n)，一个常数c和一个不违反上述定义的n0，那么f(n)在O(n)中。

这里我们只讨论输入情况的上界，这可能是最坏的输入，平均输入或任何其他输入情况。

如果算法存在“最坏输入”= w(n)和“平均输入”= a(n)，则n'0使得0 <= w(n) <= c'g(n)对于n >= n'0和存在c'，n‘0使得每n >= n’0有0 <= a(n) <= c‘g(e/n)，则可以说算法在最坏情况下是O(n)，在平均情况下是O(e/n)。

如果图表没有指定它正在考虑的f(n) (最坏的情况或平均情况)，那么我们不能肯定任何事情，图表必须更具体。

这里的常见行为是假设文本是指最坏的情况输入，这可能就是为什么我们把大O和最坏的情况联系起来的原因，而大多数情况下，这个假设有时是正确的(就像你提到的图表)--它是错误的。