Θ(deg(u)) 是什么意思？
我以前从未听说过这个，或者也许我听过其他术语？
上下文是，对于邻接表，列出与 u 相邻的所有顶点的时间为 θ(deg(u))。
同理，判断(u,v)ε E是否为O(deg(u))的时间。
如果邻接列表的实现是一个数组，那么我假设在数组中查找 u 需要恒定的时间。
如果所有相邻顶点都链接到u，那么我相信列出或查找所有顶点需要O(n)时间，其中n是相邻顶点的数量。
这本质上就是 θ(deg(u)) 的意思吗？
I have never heard this before, or maybe I have heard it in other terms?
The context is that for adjacency lists, the time to list all vertices adjacent to u is Θ(deg(u)).
Similarly, the time to determine whether (u,v)∈ E is O(deg(u)).
If the implementation of the adjacency list is an array, then I assume it would be constant time to find u in the array.
If all adjacent vertices are linked to u, then I believe it would take O(n) time to list or find all vertices, where n is the number of adjacent vertices.
Is that essentially what Θ(deg(u)) means?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
θ(deg(u))=u度数的 Big-Theta = 时间受到顶点度数的严格限制（从上方和下方限制）。在图的邻接表表示的情况下，顶点u的度是|adj[u]|u的列表的大小。因此，通过邻接列表迭代
u的相邻顶点与与u相邻的顶点数紧密绑定（算法事实有时听起来很多余，但不要这样做）他们？）。Big-O 和 Big-Theta 之间的区别在于 Big-O 是上限，而 Big-Theta 表示从上到下的紧界。也就是说，相同的表达式用作界限，但具有不同的系数 m 和 x0。请参阅 wikipedia 上的Bachmann-Landau 表示法系列。
Θ(deg(u))= Big-Theta of the degree ofu= the time is tightly-bounded (bounded from above and below) by the degree of vertices. In the case of an adjacency-list representation of the graph, the degree of a vertexuis|adj[u]|the size of the list foru.Thus, to iterate over the adjacent vertices of
uby an adjacency list is tightly-bound to the number of vertices adjacent tou(algorithmic facts sound redundant sometimes, don't they?).The difference between Big-O and Big-Theta is that Big-O is an upper bound, whereas Big-Theta states a tight bound from above and below. That is, the same expression serves as a bound, but with a different coefficient m and x0. See the family of Bachmann-Landau notations on wikipedia.
我很确定 deg(u) 的意思是“u 的度数”，即包含 u 的边数。在邻接列表表示中，该数字也将是
u的邻接列表的大小，因此迭代它需要θ(|list|)，即θ(deg(u))。I'm pretty sure
deg(u)means "the degree ofu", i.e. the number of edges that containu. In an adjacency list representation, that number will also be the size of the adjacency list foru, so iterating it requiresΘ(|list|), which isΘ(deg(u)).