0

在 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
4

1 回答 1

6

分析这个函数的主要挑战是没有那么多递归调用，但每个调用都会返回一个越来越大的元素列表。特别要注意的是有 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) 2工作。因此，在此级别上完成的总功（大致）为 (n + 1) 2 · 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)!。因此，运行时间会快速增长。

希望这可以帮助！

于 2013-05-04T18:06:39.813 回答