Час складності рекурсивних алгоритмів з гілками різної складності - великий, складний час

У мене є алгоритм

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), оскільки це найгірший випадок або ж складність щось зовсім інше в цьому випадку?

Відповіді:

Ви звичайно б плечима плечима і сказати: "Так, ця гілка має O (x), і тому вона" принаймні, що погано ".

Але якщо ми трохи розумні, ми можемо бачити, що ваш алгоритм має базовий випадок, який є O (1), а потім два інших випадки: парні і непарні.

Якщо навіть, то розмір проблеми скорочується наполовину.

Якщо непарний розмір проблеми зменшується на 1 перед тим, як скоротитися навпіл (внаслідок зменшення на 1).

Найгірший сценарій полягає в тому, що після того, як кожне парне число вдвічі менше, це непарне число, але це все ще досить добре, оскільки це зводиться до O(log(n)).