2

次のことを行うプログラムがあります。

キーは一意の単語HashMap<String, Integer>を表し、値は現在までの出現回数を表します (単語が見つかるたびに増加します)。

O(n)各挿入は一定の時間であるため、この時点まではそうであると思います。

次に、ハッシュマップを繰り返し処理し、値を new に挿入しますHashMap<Integer, List<String>>。は、カウントが一致する値Stringの中に入ります。s とs で使用される操作は定数時間であるため、Listまだであると思います。O(n)HashMapList

次に、 を繰り返し処理し、をそれぞれの に出力しHashMapます。StringList

O(n)このプログラムには、複雑さを超えた何かがありますか?

4

3 に答える 3

1

つまりO(n)、単語解析アルゴリズムが線形ではない場合を除きます (ただし、線形である必要があります)。

于 2013-10-28T02:23:11.903 に答える
1

あなたは正しいですが、警告があります。ハッシュ テーブルでは、挿入と検索にそれぞれ予想O(1) 時間かかるため、アルゴリズムの予想実行時間は O(n) です。不適切なハッシュ関数を使用している場合、それよりも時間がかかる可能性があります。通常、(ほとんどの妥当なハッシュ テーブルの実装では)最悪の場合O(n 2 ) になります。

さらに、@Paul Draper が指摘したように、これは、各文字列のハッシュ コードの計算に O(1) の時間がかかり、テーブル内の文字列の比較に O(1) の時間がかかると想定しています。長さが何らかの定数によって上から制限されていない文字列がある場合、ハッシュ コードの計算に時間がかかる場合があります。実際、より正確な分析は、ランタイムが O(n + L) であるということです。ここで、L はすべての文字列の合計の長さです。

お役に立てれば！

于 2013-10-28T02:25:30.267 に答える
0

Paul Draper と templatetypedef が指摘する 2 つの問題以外に、別の潜在的な問題があります。2 番目のマップはhashmap < int,list < string > >. これにより、リストに選択した実装が（償却された）一定時間の追加を許可する場合にのみ、合計線形の複雑さが可能になります。これは、 を使用ArrayListして最後にエントリを追加する場合、または を選択LinkedListしていずれかの最後にエントリを追加する場合に当てはまります。

これはほとんどの開発者のデフォルトの選択をカバーしていると思いますので、実際には障害にはなりません。

于 2013-10-28T04:37:07.463 に答える