Выяснить сложность времени

Question

Я студент и изучаю сложность времени.Я застрял в вопросе ниже.Я искал это, но не мог найти ничего связанного.Может кто-нибудь может выяснить временную сложность приведенного ниже алгоритма или просто дать мне знать, где найти ответ.

1:  procedure MysteryAlg(x , n)
2:      if n = 0 then
3:          return 1
4:      end if
5:      if n = 1 then
6:          return x
7:      end if
8:      if n is even then
9:          return MysteryAlg(x * x, n/2)
10:     else
11:         return MysteryAlg(x * x, n/2) * x
12:     end if
13:  end procedure

Спасибо.

Answer 1

Алгоритм, который вы написали, называется «Вычисление по квадрату». Вы можете получить больше информации здесь: https://en.wikipedia.org/wiki/Exponentiation_by_squaring

Посмотрите на раздел с заголовком " Основной метод "

И для этого требуется операция O (log2 (n)). Таким образом, вы можете принять это за сложность алгоритма.