询问递归Python函数f(n)的算法时间复杂度

你的直觉是对的，这个递归函数的时间复杂度确实属于指数级，和无记忆化的递归斐波那契函数同属一个复杂度类别，只是增长底数略小。

具体分析过程： #

1. 定义时间复杂度函数T(n)为计算f(n)所需的操作次数：

   • 当n ≤ 2时，T(n) = O(1)，因为直接返回结果，没有递归调用
   • 当n > 2时，T(n) = T(n-2) + T(n-3) + O(1)，因为每次调用会触发两个递归子调用，加上常数级的加法操作

2. 求解递推关系：
   这个递推式的特征方程是x³ - x - 1 = 0，它的最大实根约为1.3247（常被称为塑料常数）。这意味着T(n)的增长速度是O(1.32^n)。

3. 和递归斐波那契对比：
   递归斐波那契的时间复杂度是O(φ^n)（φ≈1.618，黄金分割比），虽然两者的底数不同，但都属于指数级增长。而1.32^n的增长速度慢于2^n，所以O(1.32^n)是包含在O(2^n)这个大O表示中的，因此你说它和时间复杂度O(2^N)的递归斐波那契类似是完全正确的。

4. 复杂度爆炸的根源：
   这种无记忆化的递归会产生大量重叠子问题，比如计算f(n)时，f(n-5)会被f(n-2)和f(n-3)各自调用一次，随着n增大，重复计算的次数呈指数级上升，直接导致了时间复杂度的爆炸。

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