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

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)).