小编Roo*_*kie的帖子

我知道关于 BFS 的时间复杂度有很多问题：O(V+E)

然而我仍然很难理解为什么时间复杂度是O(V+E)而不是O(V*E)

我知道O(V+E)代表O(max[V,E]) ，我唯一的猜测是它与图的密度有关，而不是与算法本身有关，不像合并排序那样。复杂度始终为O(n*logn)。

我想到的例子是：

1. 带有 |E| 的有向图 = |V|-1是的，时间复杂度为O(V)
2. 带有 |E| 的有向图 = |V|*|V-1| 事实上，复杂度为 O(|E|) = O(|V|*|V|)，因为每个顶点都有一条到除自身之外的其他顶点的出边

我的方向正确吗？任何见解都会非常有帮助。

我得到了以下代码，我知道它可以工作，但我对 Haskell 完全陌生，并且有 2 个关于 where 子句的问题。

f3 :: [[Int]] -> [Int] -> [Int]
f3 [] status = status --- Base Case
f3 ([p1,p2]:tail) status
 | status !! (p1-1) == 0  = f3 tail status  --- Case 1
 | status !! (p2-1) == 1  = f3 tail newStatus1 --- Case 2
 | otherwise = f3 tail newStatus2 --- Case 3
  where newStatus1 = set status p1 0                    --- Line 7
        newStatus2 = set newStatus2Temp p1 1            --- Line …