我以前从来没有听说过这个,或者我可能以其他方式听说过?
上下文是,对于邻接表,列出与u相邻的所有顶点的时间是Θ(deg(u))
。
同理,判断是否(u,v)∈E的时间为O(deg(u))
。
如果邻接表的实现是一个数组,那么我假设在数组中找到 u 将是常数时间。
如果所有相邻顶点都链接到 u,那么我相信列出或查找所有顶点需要 O(n)
时间,其中 n 是相邻顶点的数量。
Θ(deg(u))
本质上就是这个意思吗?
最佳答案
Θ(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在维基百科上。
关于big-o - Θ(deg(u)) 是什么意思?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6820841/