временная сложность рекурсивного алгоритма

Question

Может кто-нибудь объяснить мне, как рассчитать сложность следующего рекурсивного кода:

long bigmod(long b, long p, long m) {
    if (p == 0)
        return 1;
    else
    if (p % 2 == 0)
        return square(bigmod(b, p / 2, m)) % m;
    else    
        return ((b % m) * bigmod(b, p - 1, m)) % m;
}

Answer 1

Если вы хотите быть более формальным, то вы можете написать рекуррентное отношение и использовать основную теорему для ее решения.http://en.wikipedia.org/wiki/Master_theorem

Answer 2

Это O (log (p)) , потому что вы делите каждый раз на 2 или вычитаете одно, а затем делите на два, поэтому в худшем случае действительно будет O (2 * log (p))- один для деления и один для вычитания одного.

Обратите внимание, что в этом примере наихудший и средний случаи должны быть одинаковой сложности.

Answer 3

Это o (log (N)) основание 2, потому что деление на 2

Answer 4

Он выполняется в O(log n)

В функции нет дорогостоящих операций (так как я дороже, чем возведение в квадрат или моддинг. Нет циклов и т. Д.), Поэтому мы можем просто посчитать вызовы функций.

Наилучший случай - это степень двойки, нам потребуется ровно log (n) вызовов.

В худшем случае мы получим нечетное число при каждом другом вызове.Это может сделать не более, чем удвоить наши звонки.Умножение на постоянный множитель, не хуже асимптотически.2*f(x) is still O(f(x))

O(logn)