楽しみのために、アナグラムジェネレーターを書きました。入力された単語またはフレーズを受け取り、文字をさまざまな組み合わせで再配置して、新しい単語またはフレーズを生成します。たとえば、「cat and dog」と入力すると、「can dad got」や「ant cog dad」などの内容が返されます。
友人が実行時間とは何かと尋ねましたが、この場合の計算方法がわからないことに気付きました。起動時に、単語のリスト (辞書) を読み込みます。私の場合、約 200,000 語です (これは、標準の UNIX の /usr/share/dict/web2 辞書です)。これはアプリの起動時に 1 回限りのことであり、辞書を読み込んでインデックスを作成するのに 1 秒もかからないため、実際には実行時間には影響しません。
ユーザーが単語を入力すると、アプリケーションは辞書を検索して候補単語のリストを探します。入力単語または語句からの文字のサブセットのみが含まれている場合、その単語は候補です。候補の生成はプロセスの重要でない部分であり、今のところ無視できます。
すると検索が始まります。候補リストの最初の単語を選択します。次に、入力文字列の残りの文字からその単語の文字を削除します。次に、候補を検索して、新しく削減された入力文字列のサブセットのみを含む残りの単語を探します。次に、新しい縮小された入力単語と縮小された候補リストを使用して再帰します。候補がなくなるか、入力文字列がすべて使い果たされるまで、これを繰り返します。
そのため、検索する必要がある 100 の候補から開始する場合があります。1 つを選択し、同じ文字を持つ他のものを削除した後、90 個、50 個、または 10 個残っている可能性があるため、再帰的に検索するたびに異なる番号が残っています。これが、実行時間を理解するのに苦労している理由です。
リストから単語をまったく削除しなかった場合、それは O(n!) になります。ここで、n は候補の数です。しかし、反復ごとに積極的にリストをトリムしているため、結果は n! よりはるかに小さくなります。たとえば、私が試した 1 つのフレーズは、4,000 を超える候補を生成し、600,000 を超える組み合わせを見つけることになります。最近のノートブック コンピューター (シングル コアのみを使用) でこれを行うのに約 30 秒しかかからないため、明らかに O(n!) ではありません。
実行時間を理解するために、各反復などで候補のリストが平均してどれだけトリミングされるかについての統計が必要ですか?
各反復でリストから 10 の候補を削除すると、100 の候補リストは次のようになると考えていました: 100 * 90 * 80 * 70... または、より一般的には、n * (n - 10) * (n - 20) * (n - 30)... O(n^10 - a*n^9 - b*n^8 ...) になる 100 個の候補リストの場合。
私はそれを正しく計算しましたか、それともそれ以上のものがありますか?