0

我目前正在做一些修改，特别是对 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)!)- 这是正确的，如果是这样，这个解决方案是如何产生的，因为我无法解决？

4

1 回答 1

1

通常（但不总是）对于图，输入大小n是图中的节点数。向我们自己证明该函数（更不用说运行时）至少被调用n多次是相当容易的——通过图的单个路径（假设它是连接的，也就是说，每个节点都可以通过某个路径从每个其他节点到达）将采取'n' 个电话。

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

要查看最坏情况的运行时是O((n-1)!)，请考虑在完全连接的图中有多少条路径 - 您可以直接从任何节点访问任何节点。另一种表述方式是，您可以按任何顺序访问节点，保存起始状态。这与 (n-1) 个元素的排列数相同。我相信它实际上会是O(n!)，因为我们正在迭代O(n)路径上每个状态的所有边（n*(n-1)!）。编辑：更准确地说，我们可以说它是big-omega(N!). 有关更多详细信息，请参阅评论。

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

于 2011-05-06T21:08:35.730 回答