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))= 度数的 Big-Theta u= 时间由顶点度数严格限制（从上到下有界）。在图的邻接列表表示的情况下，顶点的度数u是|adj[u]|列表的大小u。

因此，通过邻接列表迭代相邻顶点与相邻顶点的u数量紧密相关u（算法事实有时听起来是多余的，不是吗？）。

Big-O 和 Big-Theta 之间的区别在于 Big-O 是一个上限，而 Big-Theta 表示从上到下的紧密界限。也就是说，相同的表达式用作界限，但具有不同的系数 m 和 x0。请参阅维基百科上的 Bachmann-Landau 符号系列。

Answer 2

我很确定deg(u)的意思是“程度u”，即包含u. 在邻接列表表示中，该数字也将是 的邻接列表的大小u，因此迭代它需要Θ(|list|)，即Θ(deg(u))。