我正在寻找我的代码的复杂性计算。它只是 DFS 中的 DFS（深度优先搜索）。DFS 从头到尾（向后搜索）在图（状态机）上运行。每当它到达开始时，它就会累积使其到达开始的字符串，并在另一个具有另一个 DFS 的图上尝试该字符串，以检查它是否也在具有相同字符串的另一个图上达到开始状态。
外部 DFS 复杂度定义为 O(Vo+Eo)，其中 Vo：外部图中的顶点数和 Eo：外部图中的边数。但是，当知道将要遵循的字符串时，DFS 内部的复杂性是什么？
如果可能的话，你能回答算法的整个复杂性吗？
我不确定是 O((Eo+Vo)+(Ei+Vi)) 还是 O((Eo+Vo)(Ei+Vi)) 还是 smtg .else
先感谢您，
这取决于您在第二个 DFS 失败时执行的操作。通过失败我的意思是告诉你第二个图不包含在第一个 DFS 中找到的字符串。
如果第二个 DFS 失败意味着您回溯并在第一个 DFS 中搜索另一个字符串，然后再次尝试第二个 DFS，那么您的复杂性是O((Eo+Vo)*(Ei+Vi))因为在最坏的情况下，您可能会为每个 DFS 路径执行第二个图的完整 DFS第一个 DFS 中的起始节点。
如果第二个 DFS 失败意味着您停止了，那么您最多只能对第一个图执行单个 DFS，对第二个图执行单个 DFS，这会给您带来O((Eo+Vo)+(Ei+Vi))最坏情况的复杂性。
您正在 DFS 以检查图形是否包含字符串这一事实意味着在某些情况下您可以提前终止您的 DFS（例如，您到达一个未开始的顶点，没有剩余要检查的字符）。但是，您是否能够提前终止完全取决于图的结构，所以我会说第二个 DFS 仍然是最坏的情况O(Ei+Vi)，因为对于一个讨厌的图，您可能仍然会发现自己经历了所有的边缘和所有的顶点。