计算递推关系式T(n)=2T(n/4)+5的步数及时间复杂度，求Big O表示法

嘿，这个递推式的求解其实挺直观的，我给你两种方法来拆解它——先从最基础的递推展开入手，再用主方法快速验证，这样你能彻底搞明白~

一、递推展开法（计算精确执行步数） #

为了方便计算，我们先假设n是4的幂（即n=4^k，其中k是正整数），最后再推广到一般情况：

1. 逐步展开递推式：

   • 初始式：T(n) = 2T(n/4) + 5
   • 第一次代入T(n/4)：T(n) = 2*(2T(n/4²)+5) +5 = 2²T(n/4²) + 2*5 +5
   • 第二次代入T(n/4²)：T(n) = 2³T(n/4³) + 2²*5 +2*5 +5
   • 重复展开k次后，n/4^k=1，此时T(1)=1，得到最终展开式：

     T(n) = 2^k * T(1) + 5*(2^{k-1} + 2^{k-2} + ... + 2^0)
     

2. 化简表达式：

   • 首先，k = log₄n，所以2^k = 2^{log₄n} = n^{log₄2} = n^{1/2}（因为log₄2 = 1/2）
   • 然后计算等比数列的和：2^{k-1} + 2^{k-2} + ... + 2^0 = 2^k -1 = n^{1/2} -1
   • 代入T(1)=1，最终得到：

     T(n) = n^{1/2} + 5*(n^{1/2}-1) = 6√n -5
     

3. 推广到非4的幂的情况：
   如果n不是4的幂，我们可以用向下取整或向上取整来处理n/4，最终的执行步数会和6√n -5渐近等价，不会影响时间复杂度的结论。

二、主方法（快速分析时间复杂度） #

对于标准形式的递推式T(n) = aT(n/b) + f(n)，我们可以用*主方法（Master Theorem）*直接判断时间复杂度：

• 这里a=2（子问题数量），b=4（子问题规模缩小的倍数），f(n)=5（额外执行的常数操作）
• 计算log_b a = log₄2 = 1/2
• 观察f(n)的量级：f(n)=5 = O(n^{1/2 - ε})（其中ε=1/2，满足ε>0），符合主方法的第一种情况
• 因此时间复杂度为Θ(n^{log_b a}) = Θ(√n)，用Big O表示法就是O(√n)

总结 #

• 精确执行步数（当n为4的幂时）：6√n -5
• 时间复杂度（Big O表示）：O(√n)

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