Python 中字符串排列的大 O 表示法

Question

def permutation(str): #str = string input

    if len(str) == 0:

        return [""]

    result = []

    for i, char in enumerate(str):

        for p in permutation(str[:i] + str[i + 1 :]):

            result.append(char + p)

    return result

我对这段代码中的渐近分析（时间复杂度）感到困惑，它是 O(n!) 还是 O(n*n!)，因为递归调用在循环中。我仍然很困惑，大 O 表示法是否仅基于常规表示法，如对数、线性、二次、指数、阶乘等。或者可以超出这一范围，例如不仅基于常规表示法的组合

我已经尝试计算它并在youtube上看到一些解释，但仍然不太理解。

Answer 1

你说得对，递归调用是在循环中，但是像这样排列字符串的时间复杂度简直就是

O(n!)

一种思考方式是，从

n

全部字母中选择一个字母作为排列（外部 for 循环）中的第一个字母，然后对其余字母重复该过程，留下输出您刚刚选择的字母。然后一次又一次重复，直到达到长度零。

对于每个

n

元素，您执行

n - 1

操作，然后对于每个

n - 1

元素，您执行

n - 2

操作，等等。因此，完整的递归是从

n * (n - 1) * (n - 2) ...

构建的，这相当于

 n!