Каково время работы этих функций?

Question

Какое время работает?

def a(n): 
    if n % 2 == 0: 
     return n 
    else: 
     return a(n/2) 

Мое предположение T (n) = T (n/2) + 1, затем используйте основную теорему.

---

Как насчет этой функции:

def b(n): 
    for i in range(n): 
     print(a(i)) 

Это мое предположение.

Т (п) = пТ (п/2) + 1

Answer 1

Первый из них представляет собой О (LogN) вторая представляет собой О (NlogN).

1) Вы разрешаете проблему пополам на каждой итерации. Таким образом, общее количество раз вы итерация является:

я такой, что 2 ** я = N, в математике я = LogN в базе 2. Там для O (LogN)

2) Вы перебор весь список размеров N, так что O (N), но вы вызываете функцию logN на каждой итерации. Таким образом, мы вызываем функцию logN N раз. Это O (NlogN).