2

一連の単語を含むファイルがあるとします。

1) 単語を格納するハッシュ テーブルを選択した場合 -> カウント、特定の単語の出現を見つけるための時間の複雑さはどのくらいになりますか?

2) アルファベット順にそれらの単語を返すにはどうすればよいですか?

ハッシュ テーブルを選択した場合、1) の時間計算量は、すべての単語を解析するのに O(n)、特定の単語の数を取得するのに O(1) になることがわかっています。

ハッシュテーブルを注文する方法と、時間の複雑さがどうなるかわかりません。何か助けはありますか？

4

3 に答える 3

2

ソート可能なハッシュ マップは、本質的にバイナリ ツリーになります。Java では、ルックアップと挿入で O(log n) を使用して SortableMap インターフェースを実装する TreeMap を確認できます。

最高の理論的パフォーマンスが必要な場合は、O(1) ルックアップと挿入で HashMap を使用し、表示/反復に O(n) でバケット/基数ソートを使用します。

実際には、文字列に対して基数ソートを使用すると、クイック ソート O(n log n) よりもパフォーマンスが低下します。

于 2013-02-06T16:48:44.393 に答える
0

ハッシュテーブルの操作には 2 つの欠点があります。1- データをソートされた方法で保存しない、2- ハッシュ値の計算に通常時間がかかる。また、最悪の場合、挿入/削除/検索の線形の複雑さもあります。

私の提案は、Trieを使用して単語を保存することです。挿入/検索用に保証された O(1) (単語数) があります。トライを事前注文トラバースすると、トライ内の単語のソートされたリストが得られます。

于 2013-02-06T19:43:04.473 に答える
0

(1)のあなたの分析は正しいです。

ほとんどのハッシュ テーブルの実装 (私が知っている) には、暗黙的な順序付けはありません。

順序付きリストを取得するには、リスト ( ) をソートする必要があり、リストO(n log n)に対するクエリはO(log n).

理論的には、並べ替えを行うハッシュ操作と実装を定義できますが、(効率的にするために) 十分に分散させることは難しく、並べ替えだけの方がはるかに簡単です。

多数の重複を含むファイルの場合、最初にハッシュを使用して重複を排除し、次にハッシュ テーブルを反復処理して重複していないリストを取得し、それを並べ替えるのが最善の方法です。

于 2013-02-06T16:26:17.677 に答える