Как определить временную сложность этого алгоритма?

Question

Следующая функция вычисляет a^b. предположим, что у нас уже есть первичный список, который содержит все необходимые простые числа и сортируется от малого до большого. Код написан на python.

def power(a,b): 
    if b == 0: 
     return 1 

    prime_range = int(sqrt(b)) + 1 
    for prime in prime_list: 
     if prime > prime_range: 
      break 
     if b % prime == 0: 
      return power(power(a, prime), b/prime) 

    return a * power(a, b-1) 

Как определить его временную сложность? стр. Код не идеален, но, как вы видите, идея использует простые числа, чтобы уменьшить количество арифметических операций. Я все еще ищу идеальную реализацию, поэтому, пожалуйста, помогите, если вы придумаете что-то. Спасибо!

Answer 1

Худший случай, когда для петли exausted. Но в этом случае b становится разделенным на 2 в следующем рекурсивном вызове.

В худшем случае мы разделим Ь на коэффициент 2 в приблизительно SQRT (б) операции на каждом шаге до б досягаемости 1.
Таким образом, если мы устанавливаем уравнения

F (1) = 1 и Р (п) = F (п/2) + SQRT (п)

мы получаем using woflram alpha

F (п) = (1 + SQRT (2)) (SQRT (2) SQRT (п) -1)
и это
O (sqrt (b))