零和数组最大零和划分算法的时间复杂度分析与优化咨询

问题描述 #

给定一个总和为0的数组，找出其最大划分数量，使得每个划分的子集总和均为0。

示例 #

• 输入：[-2, 4, -3, 5, -4]
• 输出：2（对应划分[[5, -2, -3], [-4, 4]]，算法无需输出具体划分）

我的解法 #

思路：从初始数组中找到任意一个总和为0的真子集（代码中的f函数用于查找该子集），其补集也满足总和为0的条件。随后对得到的子集递归执行相同算法，直到无法再划分为止。

def return_n_subsets(balances):
    balances.sort()
    
    n = len(balances)
    if n == 0:
        return 0

    @cache
    def f(sp, cur_sum):
        if sp == len(balances):
            return None
        if balances[sp] == -cur_sum:
            return [balances[sp]]
        
        if cur_sum > 0: # 提前终止，因为后续都是正数，无法凑出负的cur_sum
            return None
        # 包含当前元素
        out1 = f(sp+1, cur_sum + balances[sp])
        if out1 is not None:
            out1 = out1[:]  # 复制列表避免修改缓存的结果
            out1.append(balances[sp])
            if len(out1) != len(balances): # 确保返回的不是原数组本身
                return out1
        # 不包含当前元素
        out2 = f(sp+1, cur_sum)
        if out2 is not None:
            out2 = out2[:]  # 复制列表避免修改缓存的结果
            return out2
        return None

    sub1 = f(0,0)
    if sub1 is None:
        return 1
    [balances.remove(i) for i in sub1]
    subsets = [sub1, balances]
    out = 0
    while True:
        new_subsets = []
        for balances in subsets:
            balances.sort()
            f.cache_clear()
            sub1 = f(0, 0)
            if sub1 is not None:
                [balances.remove(i) for i in sub1]
                new_subsets.append(balances)
                new_subsets.append(sub1)
            else:
                out += 1
        if len(new_subsets) == 0:
            break
        subsets = new_subsets
    return out

我的时间复杂度计算 #

遍历原数组的所有子集，每次迭代还会复制输出列表（代码中标注的行），这部分复杂度为N×2^N。之后得到两个大小为N/2的子集，执行2×(N/2)×2^(N/2)的计算，接着是4×(N/4)×2^(N/4)，依此类推。
总体时间复杂度：O(N×2^N + N×2^(N/2) + N×2^(N/4) + ...) = O(N×(2^N + 2^(N/2) + 2^(N/4) + ...)) = O(N×2^N)

疑问 #

1. 我的时间复杂度计算是否准确？我感到困惑的是，由于使用了记忆化（memoization），实际只需解决N×S个问题，其中S是可能的和的范围（从所有负数之和到所有正数之和），不确定哪种计算正确。
2. 我可以对该算法做出哪些改进？

解答 #

关于时间复杂度的准确性 #

你的两种分析方向都有道理，但实际复杂度介于两者之间，更接近O(N×S)，不过要注意S的规模：

• 你最初按子集遍历的O(N×2^N)是最坏情况的上界，但记忆化会大幅减少重复计算。f(sp, cur_sum)的状态数是N×S，其中S是可能的和的绝对值的最大值的两倍（因为数组总和为0，所以最大正和等于最小负和的绝对值）。比如如果数组元素都是-k到k之间的整数，S是N×k，此时复杂度是O(N²k)；如果元素是任意整数，S可能很大，但实际中记忆化还是会比暴力遍历子集高效得多。
• 你拆分后的迭代计算（N×2^N + N×2^(N/2)+...）其实假设了每次都能把数组拆成两个等大的子集，但这不是必然的——比如某些数组只能拆出一个很小的零和子集，剩下的大数组还要继续处理，这种情况下后续的计算量不会像你说的那样指数级下降，所以这个分析的假设不成立，结论也就不准确。

所以更准确的时间复杂度应该是**O(K×N×S)**，其中K是最终划分出的子集数量（最多是N，当每个元素都是0时），因为每个子集都需要调用一次f函数，每次f的状态数是N_i×S_i（N_i是当前子集的大小，S_i是该子集的和范围）。

算法改进建议 #

1. 优先拆分最小的零和子集
   当前的f函数返回找到的第一个零和真子集，但为了最大化划分数量，应该优先找最小的零和子集：比如单个0元素，或者两个互为相反数的元素。拆出越小的子集，剩下的数组能拆分的次数越多。可以先遍历数组，把所有0元素单独拎出来（每个0都是一个有效划分），再检查非零元素中的相反数对，优先拆分这些对。

2. 避免不必要的列表复制
   你在f函数里每次返回结果都复制列表（out1[:]），这是因为缓存的结果会被修改。可以调整逻辑：在递归返回时直接构造新列表，比如return [balances[sp]] + out1，这样就不需要复制，能节省时间和空间。

3. 优化记忆化的使用
   当前每次处理新子集时都会cache_clear()，其实可以把f函数定义在循环内部，或者为每个子集创建独立的记忆化函数，这样就不需要清空缓存，避免重复初始化的开销。

4. 替换低效的list.remove操作
   balances.remove(i)的时间复杂度是O(N)，如果子集大小是k，移除k个元素的时间是O(kN)。可以改用哈希表统计元素频率，或者用布尔数组标记已使用的元素，拆分时直接根据标记分离子集，时间复杂度降为O(N)。

5. 动态规划思路重构
   这个问题可以转化为：找出最多的不相交零和子集的数量。可以用动态规划，状态dp[mask]表示用mask对应的元素能划分出的最大数量（mask是二进制位表示元素是否被使用）。转移时，对于每个mask，找到所有能组成零和子集的子mask，然后dp[mask] = max(dp[mask], dp[mask ^ submask] + 1)。不过这个方法的时间复杂度是O(3^N)，适合小N场景，但能保证找到最优解。

内容的提问来源于stack exchange，提问作者figs_and_nuts