如何确定Python中递归循环的时间复杂度？

Question

在Python中生成列表的所有排列的时间复杂度是多少？以下代码需要计算其时间复杂度.我该怎么做呢？

def permute(list):
    tot_list = []
    if len(list) == 1:
        return [list]
    for permutation in permute(list[1:]):
        for i in range(len(list)):
            tot_list.append(permutation[:i] + list[0:1] + permutation[i:])
    return tot_list

Answer 1

分析此函数的主要挑战是没有那么多递归调用,但每次调用都会返回越来越大的元素列表.特别要注意有n!n个元素列表的排列.因此,我们知道如果你在一个大小为n的列表上进行递归调用,那么就会有n!元素返回.

那么让我们看看这将如何影响运行时.如果只有一个元素的列表,则时间复杂度为O(1).否则,我们假设您在列表中有n + 1个元素.那么算法

1. 在大小为n的列表上进行递归调用.
2. 对于返回的每个元素,在所有可能的位置拼接列表的第一个元素.
3. 返回结果.

我们可以通过查看递归的每个级别完成的工作来分析递归的总运行时间,这意味着我们现在将关注步骤(2)和(3).

请注意,在步骤2中,如果列表中有n + 1个元素,我们将不得不查看n!递归调用生成的排列.每个排列中都有n个元素.对于每个排列,我们创建n + 1个新列表,每个列表中包含n + 1个元素.因此,我们有n!循环迭代,每个循环执行(n + 1)².因此,在这个级别完成的总工作是(大致)(n + 1)² ·n!.我们可以注意到(n + 1)·n!=(n + 1)!,所以完成的工作可以写成(n + 1)(n + 1)!.这严格小于(n + 2)!,所以我们可以说当总共n + 1个元素时完成的工作是O((n + 2)!).(注意,我们不能说这是O(n!),因为n!= o((n + 2)!)).

所以现在我们可以说完成的工作总数是(大致说来)

1!+ 2!+ 3!+ ... +(n + 1)!

据我所知,这没有一个好的,封闭形式的公式.但是,我们可以注意到这一点

1!+ 2!+ 3!+ ... +(n + 1)!

<(n + 1)!+(n + 1)!+ ... +(n + 1)!

=(n + 2)(n + 1)!

=(n + 2)!

所以整体表达式是O((n + 2)!).同样,我们也有

1!+ 2!+ 3!+ ... +(n + 1)!

>(n + 1)!

所以整体表达式是Ω((n + 1)!).换句话说,真正的答案夹在(渐近)介于(n + 1)之间的某个地方!和(n + 2)!因此,运行时间在快速增长.

希望这可以帮助!