回溯解决方案的大 O 计算范围内的排列

Question

我有一个问题，我一直在努力解决我的解决方案时间和 space 复杂性：

给定一个整数数组（可能重复）A 和 min、low、high 是整数。找出 A 中项目的总组合数：

low <= A[i] <= high
每个组合至少有 min 个数字。
一个组合中的数字可以重复，因为它们在 A 中被认为是唯一的，但组合不能重复。例如：[1,1,2] -> 组合：[1,1],[1,2],[1,1,2] 可以，但 [1,1],[1,1], [1,2], [2,1] ... 不行。

示例：A=[4, 6, 3, 13, 5, 10], min = 2, low = 3, high = 5

在 A 中有 4 种组合有效整数的方法：[4,3],[4,5],[4,3,5],[3,5]

这是我的解决方案并且有效：

class Solution:
    def __init__(self):
        pass
    def get_result(self, arr, min_size, low, high):
        return self._count_ways(arr, min_size, low, high, 0, 0)
    def _count_ways(self, arr, min_size, low, high, idx, comb_size):
        if idx == len(arr):
            return 0
        count = 0
        for i in range(idx, len(arr)):
            if arr[i] >= low and arr[i] <= high:
                comb_size += 1
                if comb_size >= min_size:
                    count += 1
                count += self._count_ways(arr, min_size, low, high, i + 1, comb_size)
                comb_size -= 1
        return count

我使用回溯是这样的：

时间：O(n!) 因为对于每一个整数，我都会在最坏的情况下检查每个剩余的整数 - 当所有整数都可以形成组合时。

Space: O(n) 因为我最多需要在调用堆栈上进行 n 次调用，我只使用 2 个变量来跟踪我的组合。

我的分析是否正确？

此外，有点超出范围但是：我应该做一些记忆来改进它吗？

Answer 1

如果我没有正确理解你的要求，你的算法太复杂了。您可以按如下方式进行：

计算数组 B，其中包含 A 中 low 和 high 之间的所有元素。
Return sum of Choose(B.length, k) 对于 k = min .. B.length，其中 Choose(n,k) 是 n(n-1)..(n-k+1)/k!.

时间和 space 复杂度是 O(n) 如果你使用记忆来计算 Choose 函数的 numerators/denominators （例如，如果你已经计算了 5*4*3，你只需要一次乘法计算 5*4*3*2 等）。

在你的例子中，你会得到 B = [4, 3, 5]，所以 B.length = 3，结果是

  Choose(3, 2) + Choose(3, 3) 
= (3 * 2)/(2 * 1) + (3 * 2 * 1)/(3 * 2 * 1) 
= 3 + 1
= 4

Answer 2

你对时间复杂度的分析不太正确。

我明白你的意思 O(n!)：for i in range(idx, len(arr)): 循环的长度随着每次递归调用而减少，所以看起来你在做 n*(n-1)*(n-2)*....

但是，来自长度为 m 的循环的递归调用并不总是包含大小为 m-1 的循环。假设您的最外层调用有 3 个元素。该循环遍历 3 个可能的值，每个值都会产生一个新的调用。第一个这样的调用将有一个迭代 2 个值的循环，但下一个调用仅迭代 1 个值，最后一个调用立即达到您的基本情况并停止。因此，您得到的不是 3*2*1=((1+1)+(1+1)+(1+1))，而是 ((1+0)+1+0)。

使用大小为 n 的数组调用 _count_ways 所花的时间是使用大小为 n-1 的调用的两倍。要看到这一点，请考虑 size n 调用中的第一个分支，即是否选择第一个元素。首先，我们选择第一个元素，这会导致大小为 n-1 的递归调用。其次，我们不选择第一个元素，这给了我们 n-1 个元素来迭代，所以就好像我们进行了第二次递归调用，大小为 n-1.

每增加 n，时间复杂度就会增加 2 倍，因此您的解决方案的时间复杂度为 O(2^n)。这是有道理的：您正在检查每个组合，并且在一组大小 n.

中有 2^n 个组合

但是，由于您只是尝试对组合进行计数而不是对它们做任何事情，因此这是非常低效的。请参阅@Mo B. 的回答以获得更好的解决方案。

回溯解决方案的大 O 计算范围内的排列

Big O of backtracking solution counts permutations with range

python

algorithm

big-o

backtracking