字符串置换算法的时间复杂度

Question

我编写了一个简单的python算法，以返回字符串的所有可能排列的列表，如下所示：

def get_permutations(sequence):

'''
Enumerate all permutations of a given string

sequence (string): an arbitrary string to permute. Assume that it is a
non-empty string.

Returns: a list of all permutations of sequence
'''

if len(sequence) <= 1:
    return list(sequence)
else:
    return_list = get_permutations(sequence[1:])
    new_list = []
    for e in return_list:
        for pos in range(len(e) + 1):
            new_list.append(e[:pos] + sequence[0] + e[pos:])
return new_list

从这段代码中，我看到时间复杂度为O（n * n！），O（n！）是“ return_list”中元素“ e”数量增加的趋势，并且存在一个嵌套循环每次新的递归都会线性增加，所以根据我的理解，O（n）。结论是该算法总体上具有O（n * n！）复杂度。

但是，当寻找相似的解决方案时，我发现很多线程都说这种算法的最佳情况应该只有O（n！），所以我的问题是：我在复杂性分析中遗漏了某些东西还是代码不是最佳的？如果不是，我该如何正确纠正？

Answer 1

我可以看到的问题是，实际上您将序列设置为get_permutations函数的参数时，您调用序列的长度。因此，仅出于将来的了解，函数括号内的参数定义了用于该函数的局部变量。例如，以下代码将基于输入执行函数：

number = int(input("Your number: "))

def print_number(choice):
    print(choice)

print_number(number)

所以，这里发生的事情是接受问题的int输入，并使用int输入的参数运行函数print_number，并且该函数接受该参数并将其作为要打印的局部变量。

Answer 2

采用任何算法，然后生成并打印出n个不同元素的序列的所有排列。那么，既然有n！不同的排列，每个排列都有n个元素，简单地打印所有排列将花费时间Θ（n·n！）。在评估生成置换的成本时，请牢记这一点。

您上面拥有的递归置换生成代码确实确实在时间Θ（n·n！）中运行。还有一些其他生成置换的算法可以generate，但不能print时间Θ（n！）的置换，但是它们的工作原理不同。

我从经验上发现，除非您仔细查看了排列生成算法的运行时分析，否则您应该怀疑运行时为Θ（n！）。大多数算法都不会在此运行时运行，在这种情况下，分析有些微妙。换句话说：您不会错过任何东西；那里只有很多“正确的道路，但不正确的”主张。 ：-）