Какова будет сложность Big-O для рекурсивной функции, число вычислений которой колеблется с n?

Question

У меня есть функция, которая находит показатель степени, но я не совсем понимаю сложность функции.

Функция:

def expo(number, exponent):
    if exponent == 0:
        return 1
    elif exponent % 2 == 0:
        val = expo(number, exponent / 2)
        return  val * val
    else:
        return number * expo(number, exponent - 1)

Я пытался вычислить иНарисуйте график числа расчетов по экспоненте и получите такой результат: График: Экспонент: Расчеты:

1: 2, 2: 3, 3: 4, 4: 4, 5: 5, 6: 5, 7: 6, 8: 5, 9: 6, 10: 6, 11: 7, 12: 6, 13:7, 14: 7, 15: 8, 16: 6, 17: 7, 18: 7, 19: 8, 20: 7, 21: 8, 22: 8, 23: 9, 24: 7, 25: 8,26: 8, 27: 9, 28: 8, 29: 9, 30: 9

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

Я прав или у меня просто неправильное представление о н (н) нотации

Answer 1

Это хорошо известный алгоритм, называемый быстрым возведением в степень (иногда квадрат и умножение), и его сложность равна O(log(n)). В Википедии есть целая страница: https://en.wikipedia.org/wiki/Exponentiation_by_squaring

Но в случае, если вы не знали эту информацию, один из способов думать - переписать ваш алгоритм, чтобы вы могли легко найти формулу повторения. Основная сложность заключается в различной процедуре, применяемой к нечетным и четным числам. Хитрость заключается в том, чтобы сгруппировать их и сделать только один рекурсивный вызов.

def expo(number, exponent):
    if exponent == 0:
        return 1
    elif exponent % 2 == 0:
        val = expo(number, exponent / 2)
        return  val * val
    else:
        return number * expo(number, exponent - 1)  # exponent - 1 is even !

можно переписать

def expo(number, exponent):
    if exponent == 0:
        return 1
    elif exponent % 2 == 0:
        val = expo(number, exponent / 2)
        return  val * val
    else:
        return number * expo(number, (exponent - 1) / 2) ** 2

Теперь вы можете видеть, что на каждом шаге алгоритма exponent(приблизительно) делится на 2 (это больше не зависит от его четности), таким образом, сложность составляет log(n).

Answer 2

Во-первых, вы можете рассмотреть алгоритм в худшем случае. Следовательно, если T(n) - время алгоритма, наихудший сценарий - T(n) = T(n-1) + c (c - это постоянное число для сравнения, сумма, вызов функции, ...). Следовательно, T(n) = O(n).

Кроме того, утверждение I think O(n) will not be linear or quadratic не имеет смысла. Если функция находится в O(n), это означает, что она не более линейна. Следовательно, он не может быть квадратичным.

Теперь вы можете более тщательно изучить сложность времени и попытаться найти жесткую границу сложности. Поскольку, по крайней мере, один раз из двух последовательных рекурсий, мы получим четное значение для exponent (как у нас -1, если exponent нечетно), следовательно, exponent достигает 1, сне более 2 log(n) вычислений (так как показатель степени будет делиться на 2 по крайней мере в каждой 2 последовательной рекурсии). Следовательно, жесткая граница для T(n) равна O(log(n)).