穷举搜索Big-O

Question

我目前正在进行一些修改，特别是要通过Big-O符号。我已经提出了一个类似的问题（涉及不同的算法），但我仍然不确定我是否正确地采取了正确的方式。

，我看的算法是穷举搜索（又名蛮力，我相信），看起来像这样：

Input: G- the graph 
    n- the current node 
    p– the path so far 
1) For every edge nm (from n to m) in G do 
2) If m ∉ p then 
3)  p = p ∪ {m} 
4)  Exhaustive(G, m, p) 
5) End If 
6) End For 

到目前为止，我已经来到了结果，该算法O(n) - 这是正确？我怀疑它是什么，并且很想知道如何去解决它。寻找什么，每次我“计数”到底是什么，等等。我知道发生的操作的数量需要计算，但是我需要注意/计数的是什么？

编辑：我已经了解到，这个算法实际上是O((n-1)!) - 这是否正确，如果是这样，这个解决方案是如何产生的，因为我无法解决这个问题？

Answer 1

通常（但不总是）带图，输入大小n是图中节点的数量。向我们证明这个函数（更不用说运行时）至少要调用n次 - 通过图的单个路径（假设它是连通的，也就是说，每个节点都可以通过某个路径从其他每个节点到达）将会很容易拿'n'电话。

要计算递归函数的运行时间，运行时间的上限将是调用递归函数的次数乘以单次调用中函数的运行时间。

要查看最坏情况运行时是O((n-1)!)，请考虑完全连接图中有多少路径 - 您可以直接从任何节点访问任何节点。措辞的另一种方法是，您可以按任何顺序访问节点，保存起始状态。这与（n-1）个元素的排列数相同。我相信它实际上将会是O(n!)，因为我们遍历所有边，对于路径上的每个状态（n*(n-1)!）需要O(n)。 编辑：更准确地说，我们可以说它是big-omega(N!)。查看评论了解更多详情。

有时，查看算法计算的结果比实际代码更容易 - 也就是说，所有状态的基数（这里更具体，路径）。