求解下述Python实现的f6函数的时间复杂度

首先给出题目对应的函数实现：

def f6(n):
    if n > 9: 
        return 1 
    else:
        x = 1
        for i in range(0,n):
            x+= f6(n+1)
        return x

推导过程 #

先拆解函数的执行逻辑：

• 递归终止分支：当入参n > 9时，函数直接返回常数1，无循环、无嵌套调用，单步执行开销为常数。
• 当入参n ≤ 0时，Python中range(0, n)不会产生任何迭代，for循环直接跳过，函数返回x的初始值1，同样是常数级开销。
• 当入参满足1 ≤ n ≤ 9时，函数会进入for循环触发递归，但注意递归调用传入的参数是n+1，也就是参数值会逐次增大，最多增大到10就会触发终止条件，不会出现递归深度随输入增长的情况。

我们从终止条件反向算每个参数对应的总操作数，记T(k)为入参等于k时的总执行步数：

• T(10) = 1，直接返回无额外操作
• T(9) = 1 + 9*T(10) = 10，包含1次当前函数的常数操作，加9次f6(10)调用
• T(8) = 1 + 8*T(9) = 81
• 顺着这个逻辑一直算到T(1)，所有结果都是固定的常数值，不会随输入n的变化而增长。

这里要注意一个常见的误区：看到循环嵌套递归就默认是高阶多项式或者阶乘复杂度，但这个函数的递归终止阈值是固定常数9，递归方向是让参数不断增大直到触碰终止线，不管输入的n取什么值，总的执行步数都有固定上限，不会随着输入规模的扩大而增加。

最终结论 #

该函数的时间复杂度为O(1)（常数级复杂度）。

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