O（dn）でn個の文字列をソートするアルゴリズムを設計する

n個の文字列をO（dn）で並べ替えるアルゴリズムを設計するにはどうすればよいですか？dは最も長い文字列の#ofですか？O（dn）でn個の文字列をソートするアルゴリズムを設計する

出典

2016-10-05 Faisal Al-harthi

trieを使用できます。

空のトライを作成します。
すべての文字列をループし、その中に配置します。
トライの値をすべて順番に反復して出力します（Trie complexity and searchingを参照してください）。これは、下記のJean-BaptisteYunèsによって提案されています。

1の複雑さは一定です。 2と3のそれぞれの複雑さは、O（dn）です。

出典

2016-10-05 05:21:53

3番目の点は不明です。どのように文字列がソートされているかを確認していますか？ –

@SauravSahuこれは非常に単純な再帰関数です（[ここ]（http://stackoverflow.com/questions/13685687/how-to-print-all-words-in-a-を参照）トライ）実装）。ノードから開始し、現在のプレフィックスを追跡しながら、すべての子を順番に再帰的に訪問します。葉を打つと、パスに沿って合計文字列が出力されます。 –

補足：http://stackoverflow.com/questions/13032116/trie-complexity-and-searching –

O（dn）でn個の文字列をソートするアルゴリズムを設計する

答えて

関連する問題