該款項子集的問題指出：給定一組整數，是否存在一個總和為零的非空子集？通常，此問題是NP完全的。我很好奇這個輕微變體的復雜性：給定一組整數，是否存在大小k和的總和為零的子集？例如，如果k = 1您可以進行二進制搜索以找到答案O(log n)。如果為k = 2，則可以將其簡化為O(n log n)（例如，請參見從總和等于給定數的數組中查找一對元素）。如果為k = 3，則可以執行此操作O(n^2)（例如，請參見在數組中求和最接近給定數字的三個元素）。是否存在一個已知的界限可以作為函數來解決這個問題k？出于動機，我在考慮這個問題，如何將一個數組分成兩部分，以使這兩部分的平均值相等？并嘗試確定它是否實際上是NP完整的。答案在于是否存在上述公式。除非有一般解決方案，否則我對了解的最佳界限會非常感興趣k=4。
3 回答
Qyouu
TA貢獻1786條經驗 獲得超11個贊
對于k = 4，空間復雜度O（n），時間復雜度O（n 2 * log（n））
對數組進行排序。從最小的2個元素和最大lesser的2個元素開始(a[i] + a[j])，以非遞減順序計算2個元素的所有greater和，(a[k] + a[l])并以非遞增順序計算2個元素的所有和。lesser如果總和小于零，則增加總和；如果總和大于零，則增加greater一；如果總和為零（成功）或a[i] + a[j] > a[k] + a[l]（失?。?，則停止。
訣竅是遍歷所有索引，i并且j這種方式(a[i] + a[j])永遠不會減少。并且對于k和l，(a[k] + a[l])永遠不應該增加。優先級隊列有助于實現此目的：
放入
key=(a[i] + a[j]), value=(i = 0, j = 1)優先級隊列。(sum, i, j)從優先級隊列中彈出。使用
sum上述算法。把
(a[i+1] + a[j]), i+1, j和(a[i] + a[j+1]), i, j+1優先級隊列僅如果不已經使用了這些元素。為了跟蹤使用過的元素，請為每個“ i”維護一個最大使用的“ j”數組。僅使用大于“ i”的“ j”值就足夠了。從步驟2繼續。
對于k> 4
如果將空間復雜度限制為O（n），那么我將無法找到比將蠻力用于k-4值并將上述算法用于剩余4值更好的方法。時間復雜度O（n （k-2） * log（n））。
對于非常大的k 整數，線性規劃可能會有所改善。
更新資料
如果n非常大（與最大整數值相同的順序），則可以實現O（1）優先級隊列，從而提高O（n 2）和O（n （k-2））的復雜度。
如果為n >= k * INT_MAX，則可以使用具有O（n）空間復雜度的其他算法。為所有可能的k/2值之和預先計算一個位集。并使用它來檢查其他k/2值的總和。時間復雜度為O（n （ceil（k / 2）））。
添加回答
舉報
0/150
提交
取消