这段带有分支的代码的时间复杂度是多少？

Question

def p(a, b):
    if b == 0:
        return 1
    if b % 2 == 0:
        return p(a, b//2) * p(a, b//2)
    return a * p(a, b-1)

---

我知道它是 O(n) 如果代码是：

def p(a, b):
    if b == 0:
        return 1
    return p(a, b//2) * p(a, b//2)

但是，当最后有一个

return a * p(a, b-1)

的时候，我不确定时间复杂度是否会发生变化

Answer 1

复杂度不会改变，即算法的复杂度都是O(b)。

很明显，复杂度只取决于b，所以我们只考虑b的大小。

考虑 b 的二进制表示，它的长度是 log(b)。

def p(a, b):
    if b == 0:
        return 1
    return p(a, b//2) * p(a, b//2)

第二个代码中，b的每一位都会将总复杂度乘以2，所以最终的复杂度为2^log(b)，即O(b)

第一个代码其实可以用同样的方式查看。如果当前位为 0，我们将复杂度乘以 2。当当前位为 1 时，递归调用

a * p(a, b-1)

只是将当前位从 1 翻转为 0，然后再次执行相同的操作。

可能没有那么严格，但是过程显然告诉我们两者的复杂度是一样的！