我正在尝试计算以下算法的大 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 是边数。
关于algorithm - Big-O/Big-Oh 表示法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5912022/