BIG-O /大哦符号

我试图计算下列算法的大O但我很困惑，需要一些帮助：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)的计算是正确的......有人可以验证这一点吗？

编辑2：或者是O(|n|+|m|)？

来源

2011-05-06 MusTheDataGuy

不，你真的应该说你认为这是家庭作业，没有人会帮助，如果你至少没有证明你是至关重要的。 – 2011-05-06 13:21:10

我认为你应该从你的推理开始，我们会帮助你。不要为此感到尴尬，最好是证明你已经尝试过，否则我们会假设你让我们为你做你的功课:-)。 – 2011-05-06 13:22:05

@Justin我只想指出，这实际上是修订而不是作业。因此，我决定尝试通过我自己的选择来计算这个算法的Big-O。但是，如果你绝对必须知道，那么我计算它是O（n + m）。正如你所看到的，这是（几乎肯定）不正确，因为我没有看到任何Big-O导致O（x + y）... @Mark我希望这证实了我的推理！ :-D – MusTheDataGuy 2011-05-06 13:24:48

它的代价是O（n + e），其中n是节点的数量，e是边的数量。

来源

2011-05-06 13:26:53 Heisenbug

这看起来像是一个简单的图形DFS，尝试做一些简单的算法示例，并找出需要做多少次迭代，并查看它与输入值的关系（n个节点，以及m个边）

来源

2011-05-06 13:23:33

允许在所有节点G中

整合

线1和线2获取在G中的每个节点称为一次;即O（N）其中N是节点的数目
对于G中的每个边缘，行4被调用一次;即O（E），其中E是边缘的数量。
第5行为G中的每个节点调用一次（除了我们开始的节点）;即O（N）。

这使得计算O(N + E)其可自E >= N减少到O(E)。

这里假设我们只是将步骤计数为相等。在实践中，我们不知道不同步骤的相对成本。当这些插入时，复杂性可能不同。

来源

2011-05-06 13:33:24

BIG-O /大哦符号

回答

相关问题