已知递归幂函数的递推关系，如何推导其精确时间复杂度

递推式精确解推导方法 #

你得到的递推关系属于最简单的一阶等差递推，用展开迭代法几步就能算出精确结果：

1. 首先展开递推项找规律
   你已得到递推式：

T(k) = 4 + T(k-1), T(1) = 2
把递推项逐层代入展开：

T(k) = T(k-1) + 4
T(k-1) = T(k-2) +4 → 代入得 T(k) = T(k-2) + 4*2
T(k-2) = T(k-3) +4 → 代入得 T(k) = T(k-3) +4*3
...
// 展开m次后通用形式为
T(k) = T(k - m) + 4*m

2. 代入边界条件求解
   当展开到边界值k-m=1时，m = k-1，把m代入上面的通用式：

T(k) = T(1) + 4*(k-1)

你已经算出边界值T(1)=2，代入计算：

T(k) = 2 + 4*(k-1) = 4k - 2

这就是你要的精确时间复杂度结果。 #

其余两种复杂度表示的由来 #

• Tilde近似：只保留最高阶项，忽略所有低阶常数项，所以去掉4k-2里的常数-2，得到~4k
• Big-O表示：只描述增长量级，忽略最高阶项的常数系数和所有低阶项，所以得到O(k)

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