big-o - 異なる複雑さの分岐を持つ再帰アルゴリズムの時間複雑性

Question

私はアルゴリズムを持っています

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

その複雑さが何であるかは定かではありません。1 つのブランチは O(N) の複雑さを持ち、もう 1 つのブランチは O(log(N)) の複雑さを持ちます。

この場合、アルゴリズムは O(N) の複雑さを持っていると言いますか、それは最悪の場合ですか、それともこの場合の複雑さはまったく異なるものですか?

Answer 1

あなたは通常、肩をすくめて「うん、この枝は O(x) を持っているので、少なくともそれは悪い」と言うでしょう。

しかし、少し賢ければ、あなたのアルゴリズムには O(1) の基本ケースと、偶数と奇数の 2 つのケースがあることがわかります。

偶数の場合、問題のサイズは半分になります。

奇数の場合、問題のサイズは半分にカットされる前に 1 ずつ減分されます (1 減分された結果として)。

最悪のシナリオは、半分に分割されたすべての偶数が奇数になるということですが、それが に減少するので、それでもかなり良いO(log(n))です。