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|)
?
答
它的代价是O(n + e),其中n是节点的数量,e是边的数量。
答
这看起来像是一个简单的图形DFS,尝试做一些简单的算法示例,并找出需要做多少次迭代,并查看它与输入值的关系(n个节点,以及m个边)
答
允许在所有节点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: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