递归函数的Big O复杂度分析求助：主方法应用是否正确？

你的主方法应用问题点 #

你对a=1、b=3的判断是正确的，但错误地将d设为1，这是导致复杂度结论错误的核心原因。

函数执行逻辑拆解 #

• 只有当n % 3 == 0时才会触发递归，否则直接返回False，递归终止
• 递归调用时，问题规模缩小为原来的1/3（即n/3），且每次仅产生1个子调用
• 函数内的所有操作（print(n)、条件判断、取模运算）均为常数时间，因此f(n) = O(1)，对应主方法中的d=0

主方法正确分析 #

主方法的核心是比较log_b(a)与d的大小关系：

1. 若log_b(a) > d，则T(n) = O(n^{log_b(a)})
2. 若log_b(a) = d，则T(n) = O(n^d log n)
3. 若log_b(a) < d，则T(n) = O(n^d)

代入参数：log_3(1) = 0，d=0，符合第二种情况，因此时间复杂度为O(log n)

代入法验证 #

假设T(n)为处理输入n的时间：

• 当n=0或n=1时，T(n) = O(1)
• 当n%3≠0时，T(n) = O(1)
• 当n%3=0时，T(n) = T(n/3) + O(1)

展开递归链：T(n) = T(n/3) + c = T(n/9) + 2c = ... = T(n/3^k) + kc，直到n/3^k无法被3整除或等于1。当n是3的幂时，k = log_3(n)，此时T(n) = O(log n)；其他场景下k更小，复杂度不会超过O(log n)。

错误原因总结 #

你之前误将f(n)判定为线性时间（d=1），但函数内没有循环或线性遍历操作，所有步骤都是常数级，因此f(n)应为O(1)。

内容的提问来源于stack exchange，提问作者Jean-Paul Azzopardi