私は友人と一緒に宿題をしようとしています.1つの質問は、線形プローブ方法の検索、追加、および削除の平均実行時間を尋ねます。追加する開いているノードが見つかるまで、特定の数のノードをチェックする必要があるため、O(n)だと思います。検索するときは、元のインデックスから開始し、目的の番号が見つかるまで上に移動します。しかし、私の友人はそれが O(1) だと言っています。どちらが正しいですか？
20558 次
1 に答える
12
漸近的複雑性について話すときは、通常、非常に大きな n を考慮に入れます。ハッシュ テーブルでの衝突処理の場合、いくつかのメソッドは連鎖ハッシュと線形プローブです。どちらの場合も、次の 2 つのことが発生する可能性があります (質問への回答に役立ちます): 1. ハッシュ テーブルがいっぱいになるため、ハッシュ テーブルのサイズ変更が必要になる場合があります。
最悪の場合、ハッシュ テーブルをどのように実装したかによって異なります。たとえば、線形プローブでは番号が見つからず、移動を続け、探していた番号が最後にありました。O(n) 最悪の場合の実行時間は次のとおりです。連鎖ハッシュ技術に来て、衝突が発生した場合、それらを処理するために、キーをバランスのとれた二分木に格納したとします。そのため、最悪の場合の実行時間は O(log n) になります。
最良の実行時間になると、混乱はないと思います。どちらの場合も O(1) になります。
O(n) は、適切に設計されたハッシュ テーブルの平均的なケースではなく、最悪のケースで発生します。それが平均的なケースで発生し始めると、ハッシュテーブルはデータ構造内の場所を見つけられません。平均的にバランスの取れたツリーは常に O(log n) を提供し、その上にあると順序も保持されるためです。
申し訳ありませんが、残念ながらあなたの友人は正しいです。あなたのケースは最悪のシナリオで起こります。
また、より有益なもの、つまり償却された実行時間については、こちらをご覧ください:ハッシュテーブルの時間の複雑さ
于 2012-04-09T11:34:37.457 に答える