Python全排列生成代码的O(n!)阶乘时间复杂度验证咨询

你的核心判断是对的：这段代码的时间复杂度增长属于阶乘量级，但严格计算的话其上界为O(n·n!)，比纯n!的增长还要略快一点，你之前的推导没有方向性错误，只是容易漏掉字符串操作的线性开销。

逐轮逻辑开销拆解 #

• 代码采用插入法生成全排列：初始从输入字符串取1个字符作为初始排列，此时results中共有1! = 1个长度为1的排列。
• 外层while stack循环总共执行n-1次，每次取出1个剩余字符，将其插入到所有已有部分排列的所有可能位置，生成更长的排列：
  • 生成长度为k的排列时，上一轮已经产出了(k-1)!个长度为k-1的部分排列
  • 每个长度为k-1的部分排列共有k个可插入位置，对应内层range(len(partial)+1)的k次循环
  • 单轮循环结束后，新的排列总数为k * (k-1)! = k!，完全匹配k个元素全排列的总数规律
• 容易疏漏的开销点：每次执行partial[:i] + current + partial[i:]做切片和字符串拼接时，生成的新字符串长度为k，单次操作的时间开销是O(k)，不是常数时间。

把所有轮次的开销累加，总操作量的主项是n·n!，因此严格时间复杂度为O(n·n!)，但从增长量级分类来说，它确实属于阶乘级别的复杂度，和你最初的判断一致。

待核验代码原文 #

def perms(a_str):
    stack = list(a_str)
    results = [stack.pop()]
    while stack:
        current = stack.pop()
        new_results = []
        for partial in results:
            for i in range(len(partial) + 1):
                new_results.append(partial[:i] + current + partial[i:])
        results = new_results
    return results


my_str = "ABCDEFGHIJ"
print(perms(my_str))

内容的提问来源于stack exchange，提问作者Robin Andrews