递归关系式中的常数疑问：幂函数递归时间复杂度推导困惑

核心问题：混淆了「操作数大小」和「操作次数」 #

你之前写出错误递归式的根源，是把乘法里的操作数n当成了需要执行的操作次数，但时间复杂度统计的是固定耗时的基本操作的执行次数，而非操作数的数值大小。

正确分析递归式的逻辑 #

先明确几个关键点：

• 这里的整数乘法n * ...是O(1)的基本操作：因为int类型的位数固定（比如32位），计算机执行两个整数乘法的指令耗时是固定的，和n的具体数值无关。
• 递归函数pow(n,p)的时间T(p)，表示计算p次幂所需的总时间。

基于此，正确的递归式应该是：

• 当p=0或n=1时，T(p) = O(1)（直接返回1，无额外操作）
• 当p>0且n≠1时，T(p) = T(p-1) + O(1)（递归调用pow(n,p-1)后，只做了一次O(1)的乘法）

求解正确的时间复杂度 #

把递归式展开：
T(p) = O(1) + O(1) + ... + O(1)（共p次累加）
结果就是O(p)，和实际执行情况完全匹配：递归调用p次，每次对应一次乘法操作，总共p次固定耗时的操作，总时间和p线性相关。

为什么你的错误递归式不成立？ #

你写的T(p) = n*T(p-1) + O(1)，相当于假设每次递归要执行n次操作，但实际代码里的n只是乘法的一个输入值，不是循环次数或操作次数。比如n=100，p=3，代码只会执行3次乘法，而不是100次递归或100次乘法——n的大小不会改变操作的次数，只会改变乘法的结果，而结果的大小不影响操作的执行时间。

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