求解两段递归伪代码的递推关系并评估时间复杂度

第一段：F(n) 函数 #

递推关系推导 #

首先明确函数的边界规则：

• 当 n=0 或 n=1 时，F(n) = n，这是初始边界条件。
  对于n≥2的情况，我们按n的奇偶性拆分推导：
• 令 k = (n+1) // 2（整数除法，向下取整），递归调用的两个参数固定为k和k-1，对应变量a和b的取值：a=F(k)，b=F(k-1)
  1. 若n为偶数：n=2k，此时触发偶数分支逻辑，得 F(2k) = F(k) * (F(k) + 2*F(k-1))
  2. 若n为奇数：n=2k-1，此时触发奇数分支逻辑，得 F(2k-1) = [F(k)]² + [F(k-1)]²
     注：该递推实际是斐波那契数列的快速倍增计算规则，正确性可通过斐波那契定义验证。

时间复杂度评估 #

• 单轮调用的非递归操作仅为常数次算术运算，耗时为O(1)
• 每调用一次F(n)，会产生2次参数规模约为n/2的递归调用，因此时间递推式为：T(n) = 2*T(n/2) + O(1)
• 用主定理求解：a=2，b=2，log_b a = 1，大于f(n)=O(1)的阶数，因此解得T(n) = O(n)
• 特殊优化说明：如果添加记忆化缓存存储已经计算过的F(k)，每个k仅需计算一次，不同k的数量为O(logn)，此时时间复杂度可降为O(logn)

第二段：P(x,n) 函数 #

递推关系推导 #

边界条件：

• 当 n=0 时，P(x,0) = 1
  对于n≥1的情况，按n的奇偶性拆分：
• 令 k = n//2（整数除法，向下取整），递归调用得到partial = P(x,k)
  1. 若n为偶数：不需要额外乘x，得 P(x,n) = [P(x,k)]²
  2. 若n为奇数：需要额外补乘一次x，得 P(x,n) = [P(x,k)]² * x
     注：该递推是标准的快速幂（二分幂）计算规则，用于快速计算x的n次幂。

时间复杂度评估 #

• 单轮调用的非递归操作仅为常数次乘法运算，耗时为O(1)
• 每调用一次P(x,n)，仅产生1次参数规模为n/2的递归调用，因此时间递推式为：T(n) = T(n/2) + O(1)
• 递归总深度为log₂n，每一层耗时都是常数，因此解得T(n) = O(logn)

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