如何提出回溯问题的时间复杂度？

Question

给定一个列表列表，打印列表列表，其中输出中的每个列表都是输入列表中元素的组合。

例如： I/P -> [['a','b'],['c'],['d','e','f']]

o/p -> ['a','c','d'], ['a','c','e' ], ['a','c','f'], ['b','c','d'], ['b','c','e'],['b','c','f']

我想出了回溯解决方案。下面是代码。但是，我很难找到它的时间复杂度。我认为它是 O(m^n)，其中 m 是给定列表列表中最长列表的长度，n 是给定列表的长度。这样对吗？如何找到像这样的回溯问题的时间复杂度？

def helper(lists, low, high, temp):
    if len(temp) == high:
        print temp
    for i in range(low, high):
        for j in range(len(lists[i])):
            helper(lists, i+1, high, temp+[lists[i][j]])

if __name__ == "__main__":
    l = [['a','b'],['c'],['d','e','f']]
    helper(l, 0, len(l), [])

Answer 1

您正在做的是重新实施 itertools.product()。

您上面的代码等同于

import itertools

if __name__ == "__main__":
    l = [['a','b'],['c'],['d','e','f']]
    l2 = itertools.product(*l)
    for x in l2:
        print(list(x))

我认为这两种解决方案的时间复杂度都是 O（列表的数量 × 列表长度的乘积），但是 itertools.product() 会快得多，用 C 编写并适当优化。

Answer 2

针对复杂性问题：

如果有K个列表，每个长度n_k，对于k = 1,...,K，那么你需要输出的列表总数是n_1 * n_2 * ... * n_K（假设顺序没有事情）。当 n_1 = n_2 = ... = n_k.

时，您的界限明显保持并且清晰

或者，我们可以让 N = n_1 + ... + n_k 为输入列表的不相交并集的大小，并根据 N 寻找边界。对于固定的 N，最坏的情况发生在 n_1 == n_2 等时，我们得到 O((N/k)^k)。最大化 k，我们发现 k=N/e 其中 e 是欧拉数。所以，我们有 O(e^(1/e)^N) ~ O(1.44^N).

正如LeopardShark所建议的，您可以查看产品的itertools实现以供参考。它不会提高渐近速度，但由于惰性 returns.

，它会更 space 高效

更整洁的 Python 实现如下：

def custom_product(lsts):
    buf = [[]]
    for lst in lsts:
        buf = [b + [x] for b in buf for x in lst]
    return buf

如何提出回溯问题的时间复杂度？

How to come up with time complexity of backtracking problem?

python

backtracking

time-complexity