Big-O/Big-Oh符号
Big-O/Big-Oh符号
提问于 2011-05-06 21:19:04
我正在尝试计算以下算法的Big-O，但我感到困惑，需要一些帮助：
Algorithm 1. DFS(G,n)
Input: G- the graph
n- the current node
1) Visit(n)
2) Mark(n)
3) For every edge nm (from n to m) in G do
4) If m is not marked then
5) Dfs(G,m)
6) End If
7) End For
Output: Depends on the purpose of the search...我甚至不会开始说我(错误地)计算出的解决方案是什么。有没有人能帮我解释一下？
谢谢。
编辑:显然，我对O(n+m)的计算是correct...can，有人验证了吗？
编辑2:还是O(|n|+|m|)？
回答 3
Stack Overflow用户
回答已采纳
发布于 2011-05-06 21:26:53
它的成本是O(n +e)，其中n是节点的数量，e是边的数量。
Stack Overflow用户
发布于 2011-05-06 21:23:33
这看起来像是图上的一个简单的DFS，试着做一些简单的算法示例，计算出您必须进行多少次迭代，并查看这与您的输入值(n个节点和m个边)之间的关系。
Stack Overflow用户
发布于 2011-05-06 21:33:25
让我们跨G中的所有节点进行集成
- 第1行和第2行针对G中的每个节点调用一次；即O(N)，其中N是针对G中的每条边调用
- 第4行的节点数；即O(E)，其中E是边数。
- 第5行针对G中的每个节点调用一次(除了我们开始的节点)；即O(N)。
这使得计算量变得O(N + E)，从E >= N开始，计算量可以减少到O(E)。
这假设我们只是在计算相等的步数。在实践中，我们不知道不同步骤的相对成本。当插入这些插件时，复杂性可能会有所不同。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5912022
复制相关文章
相似问题
腾讯云开发者
