BFS的复杂度被认为是线性的,即O(V + E),但是有向完整图中边的总数是V *(V-1),它是图形。那么BFS会花费O(V^2)时间遍历完整的图表吗?广度优先搜索完整图的复杂度是多少?
回答
是的,我假设你已经做了数学。
O(V+E) = O(V + V*(V-1))
= O(V + V*V - V)
= O(V*V)
给出这个结果,我们可以得出结论:使用邻接表的最坏情况BFS不是线性的,而是二次的? –
@UttakarshTikku它在算法的输入大小上是线性的,这是顶点数量的二次方。 –
非常感谢!这非常有帮助! –
BFS运行在O(V + E)
时间提供的图表由邻接表结构表示。
在密集的情况下,你会看到答案将是O(V+E)
。 (表示是邻接表)。
在邻接矩阵的情况下O(V^2)
。
无论图表如何,您总是会先覆盖起点的邻居。然后再为邻居重复这个。所以你可以看到它总是需要遍历O(V+E)
时间,但这是表示使邻接矩阵变得困难。所以它将是O(V^2)
。
这是因为我们希望找到每一次什么是相邻的给定的顶点“U”,我们遍历整个数组adjmatrix[u]
,这是长度的边缘| V |
我在这里得到的是这里的顶点数和边数的关系。完整图中的边数是顶点数的函数,对于完整的有向图精确为V *(V-1)。 –
是的,但表示很重要。这就是我所说的。 – coderredoc
- 1. 时间和空间复杂度的广度优先搜索
- 2. 广度优先搜索/深度优先搜索还是定向图?
- 3. 广度优先搜索生成的节点数量是多少?
- 4. 广度优先搜索 - Java
- 5. 广度优先搜索
- 6. 广度优先搜索java.lang.NullPointerException
- 7. Java广度优先搜索?
- 8. 广度优先搜索和深度优先搜索
- 9. 深度优先搜索和广度优先搜索了解
- 10. 深度或广度优先搜索?
- 11. 优先深度优先搜索广度优先搜索或反之亦然
- 12. 实现A * - 搜索作为广度优先搜索/深度优先搜索
- 13. 广度优先与深度优先搜索的输入/输出
- 14. 广度优先或深度优先搜索
- 15. F#中的广度优先搜索(BFS)
- 16. 最差情况时间深度优先搜索的复杂度
- 17. 将广度优先搜索转换为深度优先使用Java搜索
- 18. 迭代加深深度优先搜索比深度优先搜索更高的时间复杂度?
- 19. 功能广度优先搜索
- 20. BFS代码(广度优先搜索)
- 21. 并行广度优先搜索
- 22. 如何实现广度优先搜索?
- 23. 广度优先搜索 - 标准Python库
- 24. 最短路径 - 广度优先搜索
- 25. 广度优先搜索解决难题
- 26. 广度优先搜索使用阵列
- 27. 广度优先搜索练习 - AI
- 28. 广度优先搜索错误输出
- 29. 广度优先搜索算法
- 30. 广度优先搜索不起作用
查看答案。抱歉的不便。我没有看到algirthm是BFS。检查我的答案。 – coderredoc