求解下述Python代码的时间复杂度，原判断O(n)有误

def f1(seq,thelast):
    for i in range(0,thelast):
        print(seq[i])

def f2(seq,thefirst,thelast):
    if thefirst==thelast:
        f1(seq,thelast)
    else:
        for i in range(thefirst,thelast):
            temp= seq[thefirst]
            seq[thefirst]=seq[i]
            seq[i]=temp
            f2(seq, thefirst+1, thelast)
            temp=seq[thefirst]
            seq[thefirst]=seq[i]
            seq[i]=temp

问题 #

我正在尝试分析上述Python代码的时间复杂度，原本认为它包含for循环与递归，复杂度为O(n)，但实际并非如此，请问我忽略了哪些关键点？

解答 #

这是一个生成全排列并打印的代码，你忽略的核心关键点主要有三个：

• 递归分支是阶乘级增长，而非线性：f2不是单分支的线性递归，每次循环都会生成新的递归分支。比如处理n个元素时，第一层循环执行n次，每次递归处理n-1个元素；每个n-1元素的分支又会执行n-1次循环，递归处理n-2个元素……最终递归总分支数是n!（n的阶乘），增长速度远快于线性。

• f1的调用次数是n!次，而非n次：只有递归到thefirst==thelast时才会触发f1，每个递归分支的终点对应一个唯一的全排列，总共有n!个排列，所以f1会被调用n!次。而f1本身是O(n)的循环，这部分总耗时就是O(n * n!)。

• 循环与递归的嵌套不是简单线性叠加：你可能只计算了单层级循环或单次递归的耗时，但实际上每一层递归的循环次数会和下一层的递归分支数相乘，总操作数是阶乘级累加：n*(n-1)(n-2)...1 * n = nn!，而非线性的n。

综上，这段代码的时间复杂度为O(n * n!)，核心原因是全排列的数量是阶乘级，且每个排列都要执行O(n)的打印操作。

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