如何确定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）＆middot; ñ！我们可以注意到（n + 1）＆middot; 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）!.因此，运行时间会快速增长。

希望这会有所帮助！