Python字符串排列代码时间复杂度分析：O(n!)还是O(n*n!)？

首先看你给出的排列生成代码：

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*n!)而非O(n!) #

这段代码的时间复杂度是O(n*n!)，原因如下：

• 对于长度为n的字符串，递归会分解出n个长度为n-1的子问题，每个子问题会生成(n-1)!个排列。
• 每次递归返回后，需要将当前字符与每个子排列拼接（char + p），这个拼接操作的时间是O(n)（拼接后的字符串长度为n）。
• 从递推逻辑展开：设T(n)为处理长度n字符串的时间，可得递推公式T(n) = n * (T(n-1) + (n-1)! )，最终推导结果为T(n) = O(nn!)——总共有n!个最终排列，每个排列的生成过程累计需要O(n)的字符拼接操作，总操作数为nn!量级。

Big O notation可以是常规形式的组合 #

Big O符号并不局限于单一的对数、线性、二次、指数、阶乘这类形式，完全可以是这些形式的组合，比如O(n log n)、O(n² + n log n)、你提到的O(n*n!)都是合法的表示。
Big O的核心是描述输入规模n趋向无穷大时，算法运行时间的渐近增长速率，只要表达式能准确反映这个速率，不管是单一形式还是组合形式都可以使用。

内容的提问来源于stack exchange，提问作者Alvalen Shafel