algorithm - 详尽搜索 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!)，因为我们正在遍历所有边，路径上的每个状态都需要 O(n) ( n*(n-1)!). 编辑:更准确地说，我们可以说它是big-omega(N!)。有关详细信息，请参阅评论。

有时，查看算法计算的内容比查看实际代码更容易 - 即所有状态的基数(此处更具体，路径)。