给定递归函数func1的时间复杂度是多少？请说明推导原因

你的判断不正确，该函数的实际时间复杂度为O(n)，推导过程如下：
首先给出你提问的函数代码：

def func1(n):
    if n==0:
        return (1)
    if n==1:
        return (1)
    if n==2:
        return (2)
    return (n*func1(n-3))

n=int(input())
func1(n)

推导步骤 #

• 递归函数的时间复杂度 = 递归调用总次数 * 单次递归内部操作的时间复杂度
• 单次递归内部仅包含3次条件判断、1次乘法运算、1次返回操作，所有操作都是常数级耗时，单次复杂度为O(1)
• 递归调用的终止条件是n≤2，每次调用会将输入参数减少固定值3，因此递归调用的参数序列为n、n-3、n-6……直到终止值（0/1/2），该序列的总长度为⌈n/3⌉，和输入n成线性正相关，调用次数的复杂度为O(n)
• 二者相乘得到总时间复杂度：O(n) * O(1) = O(n)

为什么O(nlogn)的判断不成立 #

O(nlogn)的复杂度通常对应每次递归将问题规模按比例缩小（比如二分场景每次缩小一半）、或者存在嵌套对数级循环的场景。该函数每次仅将问题规模减少固定常数3，不存在对数级的规模缩放逻辑，因此不会达到O(nlogn)的复杂度。

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