使用分治主方法(Master Method)分析FastPower算法时间复杂度出错原因

你推导出错的核心原因是对主方法中「递归调用外执行工作量的幂次z」的取值判断错误，其次混淆了主方法的判定条件匹配逻辑：

先明确快速幂的递推关系 #

我们设T(k)为指数值为k时FastPower算法的运行时间，从代码可以得到递推式：
T(k) = T(k/2) + O(1)
对应你用的主方法参数定义：

• 递归调用次数x=1，你的判断是对的
• 问题拆分后单份子问题的规模是原规模的1/2，对应y=2，你的判断也是对的
• 递归外的操作只有固定次数的乘法、奇偶判断，和输入规模k完全无关，属于常数时间复杂度O(1) = O(k^0)，所以z的取值应该是0，不是你认为的1。

主方法判定条件匹配 #

代入参数计算y^z = 2^0 =1，完全等于递归次数x=1，符合主方法的第二种情况，而不是你说的x < y^z。
根据主方法第二种情况的结论，最终的渐近时间复杂度是O(k^z * logk) = O(logk)，也就是快速幂的常规时间复杂度结果O(log b)。

你之前误把z取为1，才会算出y^z=2，误判为x<y^z得到错误的O(k^1)=O(k)结果。

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