求解递归函数func(n)的时间复杂度

递归执行的核心特征 #

逐行梳理逻辑可以发现两个关键特点：

• 单次函数调用内部没有嵌套循环，所有单步操作（条件判断、整数加法、返回值处理）都是常数时间开销，即单步耗时为O(1)
• 无论命中哪个分支，每轮递归仅触发1次自调用，且下一次递归的输入规模固定为当前值的1/3：
  • 当n < 2时触发递归终止，不再向下延伸调用
  • n为偶数时，直接返回func(n/3)的结果，无额外操作
  • n为奇数时，仅多一次将下层返回值和当前n相加的运算，这部分属于不改变递归规模的常数操作，不会产生新的递归分支

递归次数推导 #

从初始输入n开始，持续将输入值除以3直到结果小于2，总共需要的递归层数k满足近似关系3^k = n，换算可得k = log₃n。按照渐近复杂度的计算规则，对数的底数差异属于不影响量级的常数系数，不需要在最终复杂度里体现。

最终结论 #

整段代码的时间复杂度为O(log n)，整体耗时和输入规模n的对数值成正比。

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