具有不同复杂度分支的递归算法的时间复杂度

Question

我有算法

def alg(a):
    if a == 0:
        return 1
    elif a % 2 == 1:
        return alg(a - 1)
    else:
        return alg(a / 2)

也不确定它有多复杂。一个分支的复杂度为O(N)，另一个分支的复杂度为O(log(N))。

在这种情况下，你是说算法的复杂度是O(N)，因为这是更坏的情况，还是在这种情况下，复杂度完全不同？

Answer 1

你通常会耸耸肩说：“是的，这个分支有O(x)，所以至少有那么糟糕。”

但是，如果我们有点聪明，我们可以看到你的算法有一个基例，是O(1)，然后是另外两个情况:偶数和奇数。

如果是这样的话，问题的大小就会减少一半。

如果是奇数，问题的大小在被切成两半之前会减少1(由于减少了1)。

最坏的情况是，在每将偶数减半后都是一个奇数，但这仍然相当好，因为这会减少到O(log(n))。