如何推导给定递归函数的时间复杂度T(n)的递推式

已推导内容校验 #

• 基准情形定义T(n) = c (1>=n)完全正确：数组规模≤1时，函数直接执行返回操作，仅需固定常数时间c，符合递归边界的常规设定。
• 左半段递归调用function(A,p,q)对应的复杂度T(⌊(n+1)/2⌋)计算正确：函数内取q为(p+r)//2，左半段子数组范围为[p, q]，当初始调用对应数组规模n（p=1, r=n）时，左半段长度恰好为⌊(n+1)/2⌋，复杂度匹配无误。

右半段递归的复杂度计算 #

针对function(A,q+1,r)对应的复杂度，可通过子数组实际长度直接推导：

• 右半段子数组范围为[q+1, r]，长度计算公式为r - (q+1) + 1 = r - q
• 代入q的取值、初始p=1、r=n的调用场景，化简后右半段长度为*⌊n/2⌋*，因此对应递归复杂度为T(⌊n/2⌋)

完整递推式整理 #

函数内部除两次递归调用外，无循环、遍历等线性操作，所有非递归步骤（q值计算、边界判断、返回操作）均为常数级开销，最终完整递推关系为：

• 边界条件：当 n ≤ 1 时，T(n) = c（c为固定常数）
• 递归条件：当 n > 1 时，T(n) = T(⌊(n+1)/2⌋) + T(⌊n/2⌋) + c

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