コードの複雑さの計算を探しています。これは、DFS の単純な DFS (深さ優先検索) です。DFS は、グラフ (ステート マシン) 上で端から端まで (逆方向検索) 実行されます。開始に到達するたびに、開始に到達した文字列を蓄積し、別の DFS を使用して別のグラフでその文字列を試行し、同じ文字列で他のグラフの開始状態にも到達するかどうかを確認します。
外側の DFS の複雑さは、明確に O(Vo+Eo) です。ここで、Vo : 外側のグラフの頂点の数、Eo : 外側のグラフのエッジの数です。しかし、後に続く文字列がわかっている場合、DFS 内部の複雑さはどのようなものでしょうか?
また、可能であれば、アルゴリズムの複雑さ全体についても答えていただけますか?
O((Eo+Vo)+(Ei+Vi)) か O((Eo+Vo)(Ei+Vi)) か smtg .else かはわかりません
前もって感謝します、
It depends on what you do in case the second DFS fails. By failing I mean tells you that the second graph does not contain the string found in the first DFS.
If the second DFS failing means you backtrack and search for another string in the first DFS and then try the second DFS again, then your complexity is O((Eo+Vo)*(Ei+Vi)) because you may in the worst case do a full DFS of the second graph for every single DFS path to the start node in the first DFS.
If the second DFS failing means you stop, then you will at worst perform a single DFS of the first graph and a single DFS of the second graph giving you a O((Eo+Vo)+(Ei+Vi)) worst case complexity.
The fact that you are DFSing to check if the graph contains a string means that in some cases you may be able to terminate your DFS early (for example you reach a non-start vertex with no characters remaining to check). However, whether you will be able to terminate early depends entirely on the structure of the graph so I would say that the second DFS is in the worst case still O(Ei+Vi) because with a nasty graph you may still find yourself going through all the edges and all the vertices.