A D*_*A D 3 big-o analysis adjacency-list
我以前从未听过这个,或者我用其他方式听过这个？
上下文是对于邻接列表,列出与u相邻的所有顶点的时间是?(deg(u)).
类似地,确定是否(u,v)∈E的时间O(deg(u)).
如果邻接列表的实现是一个数组,那么我认为在数组中找到u将是恒定的时间.
如果所有相邻顶点都链接到u,那么我认为O(n)列出或找到所有顶点需要时间,其中n是相邻顶点的数量.
这基本上?(deg(u))意味着什么？
?(deg(u))= =的大-Theta u=时间是由顶点的程度紧密限定的(从上方和下方限定).在图的邻接列表表示的情况下,顶点的程度u是|adj[u]|列表的大小u.
因此,u通过邻接列表迭代相邻顶点紧密地绑定到邻近的顶点的数量u(算法事实有时是多余的,不是吗？).
Big-O和Big-Theta之间的区别在于Big-O是上限,而Big-Theta表示从上到下的紧密界限.也就是说,相同的表达式用作边界,但具有不同的系数m和x0.请参阅维基百科上的Bachmann-Landau符号系列.