Как рассчитать сложность времени для следующего алгоритма

Question

Как рассчитать сложность по времени для следующего алгоритма. Я пытался, но меня путают, потому что рекурсивные звонки.

power (real x, positive integer n) 
//comment : This algorithm returns xn, taking x and n as input 
{ 
    if n=1 then 
    return x; 
    y = power(x, |n/2|) 
    if n id odd then 
    return y*y*x //comment : returning the product of y2 and x 
    else 
    return y * y //comment : returning y2 
} 

Может кто-нибудь объяснить в простых шагах.

Answer 1

Чтобы выяснить временную сложность рекурсивной функции, вам необходимо вычислить количество рекурсивных вызовов, которые будут выполняться в терминах некоторой входной переменной N.

В этом случае каждый вызов выполняет не более одного рекурсивного вызова. Количество вызовов составляет порядка O (log N), так как каждый вызов уменьшает N пополам.

Остальная часть тела рекурсивной функции O (1), поскольку она не зависит от N. Поэтому ваша функция имеет временную сложность O (log N).

Answer 2

Каждый вызов считается постоянной работы время, и сколько раз это будет рекурсию равно, сколько раз вы можете сделать п/2, прежде чем п = 1, что в лог (n) раз. Поэтому наихудшее время работы - O (log n).