8

私は答えを求められたこの質問に汗を流してきました（技術的には宿題です）。私はハッシュテーブルを検討しましたが、これをどのように機能させるかについての正確な詳細に固執しています

ここに質問があります：

整数のkセットA1、A 2、..、合計サイズO（n ）のA kが与えられた場合 、1 ϵ A 1、a 2 ϵ A 2、.. 、ak ϵ A k、a 1 + a 2 + .. + a k −1 = akとなるように。アルゴリズムはTk （n）時間で実行する必要があります。ここで、T k（n）= O（n k /2 ×logn ）（偶数kの場合） 、O（n （k +1）/ 2 ）（ kの奇数値の場合）。

私がこれを解決することに近づくことができるように、誰かが私に一般的な方向性を与えることができますか？

4

1 に答える 1

9

kセットを2つのグループに分けます。kが偶数の場合、両方のグループにそれぞれk/2セットがあります。奇数kの場合、一方のグループには（k + 1）/ 2があり、もう一方のグループには（k-1）/2セットがあります。各グループ内のすべての可能な合計（各セットから1つの要素を取得）を計算します。kが偶数の場合、それぞれがn k/2要素の2つの配列を取得します。奇数kの場合、一方の配列にはn （k + 1） / 2の要素があり、もう一方の配列にはn （k-1）/2の要素があります。問題は標準の問題になります。「2つの配列がある場合、各配列から1つの要素を取得することで、指定された合計に到達できるかどうかを確認してください」。

于 2011-12-17T16:07:58.520 に答える