使用展开法分析递归算法Trump的运行时间

嘿，咱们来一步步拆解这个Trump算法的运行时间，用展开法来分析最直观不过了～首先先明确：输入的n是不小于1的2的幂次，所以咱们可以把n写成2^k的形式（k是≥0的整数），这样分析起来更顺畅。

第一步：定义时间复杂度函数T(n) #

先给每个操作的时间打个标：

• 当n=1时，“点一份鸡块”是常数时间，记为T(1) = c₁（c₁是固定常数）
• 当n=2时，“喝一品脱啤酒”也是常数时间，记为T(2) = c₂（c₂是固定常数）
• 当n>2时，执行print "I am fabulous"是常数时间c₃，然后递归调用Trump(n/2)，所以递归式为：

  T(n) = c₃ + T(n/2)
  

第二步：展开递归式 #

咱们拿具体的例子先热身，再推广到一般情况：
比如n=8（也就是2^3）：

T(8) = c₃ + T(4)
T(4) = c₃ + T(2)
T(2) = c₂

把这些代入回去，得到：

T(8) = c₃ + (c₃ + c₂) = 2c₃ + c₂

再看n=16（2^4）：

T(16) = c₃ + T(8) = c₃ + (2c₃ + c₂) = 3c₃ + c₂

现在找规律：对于n=2^k（k≥2，也就是n>2），咱们可以展开k-1次，直到递归到n=2的终止条件：

T(n) = c₃ + T(n/2)
     = c₃ + c₃ + T(n/4) = 2c₃ + T(n/4)
     = 2c₃ + c₃ + T(n/8) = 3c₃ + T(n/8)
     ...
     = (k-1)c₃ + T(2)
     = (k-1)c₃ + c₂

第三步：把k换回n的表达式 #

因为n=2^k，所以k = log₂n（以2为底的对数）。把k代入上面的式子：

T(n) = (log₂n - 1)c₃ + c₂
     = c₃·log₂n + (c₂ - c₃)

最后总结时间复杂度 #

从上面的式子能看出来，T(n)是关于log₂n的线性函数，忽略常数项和系数的话，这个算法的时间复杂度是O(log n)。

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