私はデータ構造試験を勉強していて、この質問を解決しようとしています:
n 個の数値の配列と数値 Z が与えられた場合、 x+y=Z などの x,y を O(n) 平均時間で見つけます。
私の提案は、配列の内容をハッシュ テーブルに移動し、オープン アドレッシングを使用して次のことを行うことです。
各数値 A[i] に対して、ハッシュ テーブル内の ZA[i] を検索します (各操作の平均で O(1)。) 最悪の場合、n 回の検索を実行し、それぞれの平均時間は O(1) であり、それは O(n ） 平均して。
私の分析は正しいですか？