为什么邻接列表中的操作是O（e/v）$？

Question

我正在为即将到来的考试而学习。提供给我的一个图表具有以下算法复杂性，总结了一个具有N个节点和E条边的图的邻接列表。

>

查找边-O（E/N）

插入边缘-O（E/N）

删除边-O（E/N）

枚举节点的边-O（E/N）

我理解邻接列表是什么--我们通过使用列表数组来存储与每个顶点相邻的顶点。但是为什么这些操作是O（E/N）呢？在我看来，如果我们取一个图，其中绘制了所有可能的边（例如，如果图是无向的，我们有n(n-1)/2条边），那么数组中的每个列表将有n-1个条目来存储每一个其他节点

Answer 1

我相信这个问题与stackoverflow上的其他问题非常相似，请参考它，因为它可能已经回答了您的问题。为了完整起见，我也会试着总结一下我对这个主题的理解，但我不是这个主题的权威，所以如果我说错了，请随时纠正：

我能理解的是，你在问为什么图表上说一个操作是O（e/N），而众所周知最坏的情况是O（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，使得对于每一个n>=n0，0<=f(n)<=cg(n)，那么f(n)在O(g(n))中。所以忘了最坏的情况吧，如果我们能提供一个函数f(n),一个常数c和一个不违反上述定义的n0则f(n)在O(n)中。
这里我们只讨论那个输入情况的上界,
如果一个算法有“最坏输入”=w(n)和“平均输入”=a(n)，其中存在一个C′，n′0，使得对每一个n>=n′0有0<=w(n)<=C'g(n)和存在一个C′，n′0，使得对每一个n>=n′0有0<=a(n)<=C'g(n)，那么我们可以说该算法在最坏情况下是O(n)，在平均情况下是O（E/n）。

如果图表没有指定它所考虑的f(n)（以最坏情况或平均情况为例），那么我们就不能肯定任何事情，图表必须更加具体。
这里常见的行为是假设文本引用的是最坏情况输入，并且，这可能就是为什么我们将大O与最坏情况联系起来的原因，而大多数时候这种假设是对的有时（就像你提到的图表）是错的。