详尽搜索 Big-O
我目前正在做一些修改，特别是讨论 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)!) - 这是正确的吗？如果是的话，这个解决方案是如何产生的，因为我无法解决？
I am working on some revision at the moment and specifically going over Big-O notation. I have asked a similar question (which dealt with a different algorithm) but am still unsure if I am going the right way about it or not.
The algorithm that I am looking at is Exhaustive Search (aka Brute Force, I believe) and looks like this:
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
So far I have come to the result that this algorithm is O(n) - is this correct? I doubt that it is, and would love to know exactly how to go about working it out; what to look for, what exactly it is that I 'count' each time, etc. I understand that the number of operations taking place need to be counted, but is that all that I need to take note of/count?
EDIT: I have learned that this algorithm is, in fact, O((n-1)!) - is this correct and if so, how did this solution come about as I cannot work it out?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
通常（但并非总是）对于图形，输入大小 n 是图形中的节点数。向我们自己证明该函数（更不用说运行时）至少被调用 n 次是相当容易的——通过图形的单个路径（假设它是连接的，也就是说，每个节点都可以从每个通过某些路径的其他节点）将进行“n”次调用。
为了计算递归函数的运行时间，运行时间的上限将是调用递归函数的次数乘以单次调用中函数的运行时间。
要了解最坏情况的运行时间是
O((n-1)!)，请考虑完全连接图中有多少条路径 - 您可以直接从任何节点访问任何节点。另一种表达方式是，您可以按任何顺序访问节点，保存起始状态。这与 (n-1) 个元素的排列数相同。我相信它实际上会是O(n!)，因为我们正在迭代所有边，这对于路径上的每个状态都需要O(n)(n*(n-1)!)。 编辑：更准确地说，我们可以说它是big-omega(N!)。查看评论了解更多详情。有时，查看算法计算的内容比实际代码更容易 - 即所有状态的基数（这里更具体，路径）。
Usually (but not always) with graphs, the input size
nis the number of nodes in the graph. It's fairly easy to prove to ourselves that the function (let alone the runtime) is called at leastntimes - a single path through a graph (assuming it's connected, that is, every node is reachable from every other node via some path) will take `n' calls.To compute running time of recursive functions, an upper bound on the running time will be the number of times the recursive function is called multiplied by the runtime of the function in a single call.
To see that the worst case runtime is
O((n-1)!), consider how many paths are in a fully connected graph - you can visit any node directly from any node. Another way of phrasing this is that you can visit the nodes in any order, save the starting state. This is the same as the number of permutations of (n-1) elements. I believe it's actually going to beO(n!), since we are iterating over all edges which takesO(n)for each state on the path (n*(n-1)!). EDIT: More precisely, we can say it'sbig-omega(N!). See comments for more details.Sometimes, it's easier to look at what the algorithm computes than the actual code - that is, the cardinality of all the states (more specificity here, paths).