big-o - Θ(deg(u)) 是什么意思？

Question

我以前从来没有听说过这个，或者我可能以其他方式听说过？
上下文是，对于邻接表，列出与u相邻的所有顶点的时间是Θ(deg(u))。
同理，判断是否(u,v)∈E的时间为O(deg(u))。
如果邻接表的实现是一个数组，那么我假设在数组中找到 u 将是常数时间。
如果所有相邻顶点都链接到 u，那么我相信列出或查找所有顶点需要 O(n) 时间，其中 n 是相邻顶点的数量。
Θ(deg(u)) 本质上就是这个意思吗？

Answer 1

Θ(deg(u)) = u 度数的 Big-Theta = 时间受度数的严格限制(从上方和下方限制)的顶点。在图的邻接表表示的情况下，顶点 u 的度数是 |adj[u]| u 的列表大小。

因此，通过邻接列表遍历 u 的相邻顶点与 u 相邻的顶点数紧密相关(算法事实有时听起来多余，不是吗？)。

Big-O 和 Big-Theta 之间的区别在于，Big-O 是一个上限，而 Big-Theta 则表示从上到下的紧界。也就是说，相同的表达式用作边界，但具有不同的系数 m 和 x0。参见 the family of Bachmann-Landau notations在维基百科上。