0

スタックへの各挿入は O(1) なので、「n」個の要素を挿入するのにかかる時間は O(n) ですか? ハッシュテーブルについても同様に話せますか? 平均的な場合、ハッシュ テーブルに「n」個の要素を挿入するのにかかる時間 = O(n) ?

4

2 に答える 2

3

はい。支配的な要因は、一定の挿入時間ではなく、挿入しているすべてのものを反復処理するのにかかる時間です。挿入が一定時間内に行われなかった場合、それはより複雑になります。

HashTableの場合、HashTableがそれ自体を成長させる必要があるのか​​、それともその中のすべてを再ハッシュする必要があるのか​​によって大きく異なりますが、単純な場合（つまり、テーブルがすべてを保持するのに十分な大きさであり、ハッシュコードの生成が生成されないと仮定する場合）衝突）インサートの上限はnでなければなりません。

于 2011-06-15T18:46:04.163 に答える
0

スタックへの各挿入は O(1) なので、「n」個の要素を挿入するのにかかる時間は O(n) ですか? ハッシュテーブルについても同様に話せますか? 平均的な場合、ハッシュ テーブルに「n」個の要素を挿入するのにかかる時間 = O(n) ?

あなたがスタックについて言及したように、スタックを使用してハッシュテーブルの衝突を解決すると仮定します（チェーン方式で、閉じたアドレス指定を使用して）。

そのような場合、私はこう答えます。

はい、「ハッシュテーブルに 'n' 個の要素を挿入するのにかかる平均時間 = O(n)」。

もう少し詳しく言うと。あなたの場合のハッシュテーブルへの挿入は次のとおりです。

  • ハッシュの作成 = O(1)
  • ハッシュ = O(1) で選択されたスタックに挿入

全体のハッシュ挿入は O(1) です。したがって、n 回の操作は O(n) です。

私のアドバイス : 仮定 (使用する構造、実装、複雑さ) について、試験では非常に具体的に説明してください。これらの詳細はすべて、すべての方程式の結果に大きな影響を与える可能性があるためです。

于 2012-01-09T15:57:15.667 に答える