今学期はアルゴリズムのコースを受講しており、CLRS の問題を解決しようとしています。
2.3-7 n 個の整数と別の整数 x の集合 S が与えられたとき、合計が正確に x である 2 つの要素が S に存在するかどうかを判定する theta(n lg n) 時間アルゴリズムを説明してください。
この問題にアプローチする方法がわかりません。nlogn時間で完了するため、マージソートアルゴリズムを使用して解決しようとしていますが、それが正しいアプローチであるかどうかはわかりません。
実行時間がすでに指定されているときにアルゴリズムを解くときの一般的なアプローチは何ですか?
ありがとう。
「アルゴリズムを提案する」タスクのように、そのような問題に対する一般的なアプローチがあるとは思えません。ただし、必要なランタイムは、使用する「ビルディング ブロック」を示唆する可能性があります (の存在は、log通常、ツリーまたは並べ替えられた配列の必要性を示します)。たとえば、「big-o」のタグ wiki で、必要な各ランタイムのアルゴリズムの例を確認できます。
問題のアルゴリズムのアイデア:
まず、配列をソートします ( O(n lg n))。次に、配列の各要素yについて、要素が存在するかどうかを確認しますx-y（またO(n lg n)、配列がソートされているため）。