如图
源课程链接
私以为,复杂度应该是 O(|V|*|E|),因为里外两层循环啊,为什么图中认为是 O(|V|+|E|)
对于这段代码来说,图中每个点和边最坏情况对会被访问一次,因此时间是 v + e.
如果是 v * e,那么相当于对于每一个点都会 check 所有边(即便是和当前点不相连),这是不可能的。
外层循环用来遍历所有点,内层循环用来遍历所有边。如果是V*E,那就成了对于每个点都处理每条边,显然不是所有的边都连接在点上的。
5 回答356 阅读✓ 已解决
1 回答582 阅读✓ 已解决
1 回答465 阅读✓ 已解决
3 回答664 阅读
2 回答346 阅读✓ 已解决
2 回答596 阅读
1 回答647 阅读
对于这段代码来说,图中每个点和边最坏情况对会被访问一次,因此时间是 v + e.
如果是 v * e,那么相当于对于每一个点都会 check 所有边(即便是和当前点不相连),这是不可能的。