以下算法的时间复杂度是多少?我可以做哪些优化?

问题描述 投票:0回答:1

问题:给定一个总和为 0 的数组,找到其最大分区数,使得所有分区的总和分别为 0。

示例:

  • 输入:[-2, 4, -3, 5, -4]
  • 输出:2(即 [[5, -2, -3], [-4, 4]]。这些不一定需要作为算法的输出)

我的解决方案:

我从初始列表中找到总和为 0 并且是真子集的任何子集(下面代码中的函数

f
发现任何子集)。它的脱节也是一个答案。然后我对我发现的结果运行相同的算法。

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: #early stop since there would be only positive numbers from here on
            return None
        #include sp
        out1 = f(sp+1, cur_sum + balances[sp])
        if out1 is not None:
            out1 = out1[:] #############################
            out1.append(balances[sp])
            if len(out1) != len(balances): #condition to not return the input itself
                return out1
        #dont include sp
        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 = 2
    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

我的时间复杂度计算:

我正在遍历原始列表的每个子集,并且在每次迭代时我还创建输出列表的副本(代码中的行后面有很多哈希值)。这是 Nx2^N。然后我得到 2 个大小为 N/2 的子集,然后运行 2xN/2x2^(N/2)。然后我运行 4xN/4x2^(N/4) 等等。

总体时间复杂度:O(Nx2^N + Nx2^(N/2) + Nx2^(N/4) ...) = O(Nx(2^N + 2^(N/2) + 2^( N/4) ...)) = O(Nx2^N)

  1. 我计算的时间复杂度准确吗? 我很困惑,因为我使用记忆化,看起来我实际上只解决 N*S 问题,其中 S 是可能的总和,范围从所有负数的总和到所有正数的总和。有点困惑哪个是准确的。
  2. 我的算法可以改进吗?
algorithm recursion time-complexity dynamic-programming memoization
1个回答
0
投票

您的问题包含 3-分区问题 几乎是一个特例。也就是说,我们能否将一个集合分成 3 个集合,每个集合的总和相同。这是强 NP 完全的。这意味着它不仅是 NP 完全的,而且不存在伪多项式近似。因此,您不应期望比指数最坏情况更好。

我没有详细分析你的复杂性,但最终结果听起来很合理。

现在我们可以更快吗?最坏的情况下?不,在实践中?让我们拿出我的旧备忘单。

  • A* 搜索
  • 子集和伪多项式近似。
  • 我个人的“将动态规划变成显式解决方案”的技巧。只是个人的,因为似乎没有人有兴趣学习如何自己做。

这是我将如何做的概述。

  1. 先按绝对值递减顺序对元素进行排序,然后再递增值。
  2. 将 0 分开。
  3. 将其转换为元组
    (abs(element), count_negatives, count_positives)
  4. 为 A* 搜索创建一个简单的上限。 (基于对 pos 的否定,希望所有其他的都变成尽可能多的 3 组。)
  5. 对最佳划分进行 A* 搜索。

所以对于你的例子来说没有0。排序后我们得到

[5, -4, 4, -3, -2]
。朴素的下界将是
2
(我们可以将
-4, 4
配对,然后除以剩余的
3
)。 A* 搜索将立即验证这是否有效。

不幸的是有两个问题:

  1. A* 搜索确实需要持久数据结构 才能有效地编码,但没有人拥有一个好的 Python 库来实现这一点。为什么需要那个?这是因为它允许你非常便宜地说,“从这个长列表中取出这里的这个元素,那里的那个元素”,而不必
  2. 我已经手动完成了太多“动态编程到显式解决方案”,接下来想为其编写一个库。这让我们可以取出第一个元素并找到其长度为 2、3、4 等的所有解决方案。然后按字典顺序尝试这些解决方案。哦,天哪,我们重复这一点,试图为下一个找到一个好的解决方案。等等。

我正在编写这两个库,但它们是中型大型项目,因此无法承诺何时完成。

但这应该让我们知道可以优化多少。

© www.soinside.com 2019 - 2024. All rights reserved.