我正在尝试在Java中实现BFS和DFS作为通用算法.我正在编写一种方法getComplexity(),将算法的最坏情况复杂性作为字符串返回.在DFS(和BFS)中,图中的每个节点只能访问一次.在最坏的情况下,每个节点只访问一次.因此,为什么这些算法的复杂性为O(V + E)而不是O(V)？这里V是节点(或顶点)的数量,E是边数.
树遍历(BFS和DFS)是O(V + E),因为每个边必须只遍历一次,每个节点必须只访问一次.树遍历通常是一种抽象,可以帮助我们查看问题.在大多数简单的情况下,V和E都是微不足道的操作,但情况并非总是如此,V的效率可能与E完全不同.例如,遍历边缘可能就像跟踪指针一样简单,或者它可能要求您通过网络从远程主机获取数据(可能涉及昂贵的数据库查询).访问节点可以像设置布尔值一样简单,也可能涉及对该节点上的数据执行一些昂贵的计算.
O(V + E)提醒我们,当我们推断遍历树的整体复杂性时,我们必须考虑访问节点和遍历边的复杂性.