すべての文字置換単語を生成するのに時間がかかりますか？

Question

「料理」などの単語があり、その単語から作成できるすべての可能な単語のグラフを、各文字を他のすべての文字に置き換えて生成したい場合を考えてみましょう。重要な制限：文字の集合が単語であるかどうかを辞書に尋ねることはできますが、それは辞書へのインタフェースの限界です。辞書にすべてのn文字の単語を尋ねることはできません。その上

          cook 
           /  |  \ 
           aook  ...  zook 
          /| \   /| \ 
          aaok ... azok  zaok ... zzok 

とを次のような私はこれを想像

は、DAGを生成する再帰アルゴリズムになります。明らかに実際にはこれらの順列の多くは実際の言葉ではないと拒否されますが、最終的には生成されるすべての「言葉」を含むDAGを持つことになります。グラフの高さは、入力語の長さに1を加えたものになります。

最悪の場合、各置換は単語になります。最初のレベルは1語、第2レベルは25、次レベル（25 * 25）などです。したがって、nが単語の長さである場合、これはアルゴリズムが最悪の場合の時間複雑度が25^nであり、最悪の場合の記憶複雑性が25^nであることを意味すると考えていますか？

Answer 1

これは、ツリーとして表示するのではなく、グラフとして表示する方が良いでしょう。

nを入力とします。これは単語の長さです。

Wをすべて長さ$ n $の意味のある単語とします。

次のように単純なグラフGを構築：Gの頂点がWあります。 w1とw2の2つの単語は、1つのチャーターで異なる場合にのみそれらを接続するエッジを持っています。

は次に何がやりたいことは以下の通りです：

Wに単語wを考えると、グラフGでwの連結成分を見つけます。

これは、通常、depth-first search（DFS）またはbreadth-first search（BFS）で行われます。あなたのアルゴリズムはBFSのようなものですが、1つの場所が置換されたものだけでなく、単語のすべての近傍を生成する必要があるたびに、正しくはありません。

我々は$ n個の小さな$をとることができるので、時間の複雑さは、理論的には（非常に大きな大きなO定数とが）結果のサイズに

を直線的であるしかし、あなたはまた、メモリの同じ大きさを持つべきですどの単語が既にチェックされているかを記憶する。

Answer 2

辞書で見つかる単語のみを生成すると、時間の複雑さは辞書のサイズによって制限されるため、O(min(|D|, 25^n))にする必要があります。