关于Do-something算法的功能解析、(2,5)示例推演及worst-case runtime分析的技术问询

嘿，咱们来一步步拆解这个算法，先搞懂它到底干啥的，再走一遍(2,5)的执行流程，最后聊聊最坏情况下的运行时间～

算法功能解析 #

其实这个函数是快速幂算法（也叫二分幂算法），核心是用来高效计算a^b（a的b次幂）的。刚开始看的时候确实容易误以为它只会返回1或者a，但每一层递归的结果会被平方（奇数情况还会多乘一次a），通过递归拆解问题，把幂运算的乘法次数从O(b)降到了O(log b)，效率提升很多。

(2,5)示例详细推演 #

咱们跟着调用栈一步步走，就能清楚看到结果是怎么来的：

1. 初始调用Do-something(2,5)：因为5是奇数，所以先计算x = Do-something(2, (5-1)/2) = Do-something(2,2)
2. 进入Do-something(2,2)：2是偶数，计算x = Do-something(2, 2/2) = Do-something(2,1)
3. 进入Do-something(2,1)：1是奇数，计算x = Do-something(2, (1-1)/2) = Do-something(2,0)
4. 进入Do-something(2,0)：触发base case（b=0），直接返回1
5. 回到Do-something(2,1)：执行x*x*a = 1*1*2 = 2，返回2
6. 回到Do-something(2,2)：执行x*x = 2*2 =4，返回4
7. 回到最初的Do-something(2,5)：执行x*x*a =4*4*2=32，最终返回32（也就是2^5的结果）

最坏-case runtime分析 #

这个算法的递归逻辑是每次把b的规模折半：

• 不管b是奇数还是偶数，每一层递归都会把b的大小缩小一半（奇数是(b-1)/2，偶数是b/2，本质都是近似折半）
• 递归的深度是log₂(b)（向下取整后加1），每一层只做常数次乘法操作（O(1)）

最坏情况出现在b是形如2^k -1的数（比如1、3、7、15...），这时候每一次递归都需要多执行一次乘法（因为b始终是奇数），但递归深度依然是O(log b)级别，所以整体的最坏时间复杂度是O(log b)。

备注：内容来源于stack exchange，提问作者user1154312